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

arXiv:2404.03842v1 Announce Type: cross
Abstract: 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 that the maximum independent set has density $\left(\frac{r\log d}{(r-1)d}\right)^{1/(r-1)}$. We show that the class of low-degree polynomial algorithms can find independent sets of density $\left(\frac{\log d}{(r-1)d}\right)^{1/(r-1)}$ but no larger. This extends and generalizes earlier results of Gamarnik and Sudan, Rahman and Virag, and Wein on graphs, and answers a question …

abstract algorithms arxiv class cs.cc cs.ds independent low math.co math.pr polynomial random set show stat.ml study type uniform