The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs

Abhishek Dhawan, Yuzhou Wang

We study the algorithmic task of finding large independent sets in Erdos-Renyi $r$-uniform hypergraphs on $n$ vertices having average degree $d$. Krivelevich and Sudakov showed tha…