The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
SIAM Journal on Discrete Mathematics · 31.03.2026 · 40 (1) · 374-419
DOI: 10.1137/24m1701575 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 17.03.2026. Verfasst von Abhishek Dhawan und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 77 Literaturangaben. Gefördert von: Georgia Institute of Technology, National Science Foundation.
Abstract (Originalsprache)
We study the algorithmic task of finding large independent sets in sparse Erdős–Rényi random [Formula: see text]-uniform hypergraphs on [Formula: see text] vertices having average degree [Formula: see text]. Krivelevich and Sudakov showed that the maximum independent set has density [Formula: see text] in the double limit [Formula: see text] followed by [Formula: see text]. We show that the class of low-degree polynomial algorithms can find independent sets of density [Formula: see text] but no larger. This extends and generalizes earlier results of Gamarnik and Sudan, Limits of local algorithms over sparse random graphs, 2014, Rahman and Virág, Ann. Probab., 45 (2017), pp. 1543–1577, and Wein, Math. Statist. Learn., 4 (2022), pp. 221–251 on graphs, and answers a question of Bal and Bennett. We conjecture that this statistical–computational gap of a multiplicative of [Formula: see text] indeed holds for this problem. Additionally, we explore the universality of this gap by examining [Formula: see text]-partite hypergraphs. A hypergraph [Formula: see text] is [Formula: see text]-partite if there is a partition [Formula: see text] such that each edge contains exactly one vertex from each set [Formula: see text]. We consider the problem of finding large balanced independent sets (independent sets containing the same number of vertices in each partition) in random [Formula: see text]-uniform [Formula: see text]-partite hypergraphs with [Formula: see text] vertices from each partition and average degree [Formula: see text]. We prove that the maximum balanced independent set has density [Formula: see text] asymptotically, matching that of independent sets in ordinary hypergraphs. Furthermore, we prove an analogous computational threshold of [Formula: see text] for low-degree polynomial algorithms, answering a question of the first author. We prove more general statements regarding [Formula: see text] -balanced independent sets (where we specify the proportion of vertices of the independent set contained within each partition). Our results recover and generalize recent work of Perkins and the second author on bipartite graphs. Our results not only pin down the precise threshold for low-degree algorithms in two different settings, but also suggest that these gaps persist for larger uniformities as well as across many models. A somewhat surprising aspect of the gap for balanced independent sets is that the algorithm achieving the lower bound is a simple degree-1 polynomial.
Förderung
- Georgia Institute of Technology
- National Science Foundation
Zitieren
APA
Dhawan, A., & Wang, Y. (2026). The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs. SIAM Journal on Discrete Mathematics, 40(1), 374-419. https://doi.org/10.1137/24m1701575
Vancouver
Dhawan A, Wang Y. The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs. SIAM Journal on Discrete Mathematics. 2026;40(1):374-419. doi:10.1137/24m1701575
BibTeX
@article{Dhawan2026,
author = {Dhawan, Abhishek and Wang, Yuzhou},
title = {The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {1},
pages = {374--419},
doi = {10.1137/24m1701575}
}
EUVIMED