Improved Certificates for Independence Number in Semirandom Hypergraphs
2026-03-09 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to efficiently find upper limits on the size of independent sets in special kinds of hypergraphs, which is usually very hard. They improve previous methods by removing extra log factors and almost reaching the best possible computational limits, especially in a tougher 'semirandom' setting where some randomness is mixed with adversarial changes. Their work uses advanced mathematical techniques called Sum-of-Squares and tensor analysis, along with new matrix concentration results, to achieve these improvements. They also show their methods help identify hidden colorings in these hypergraphs even when strong adversaries try to hide them.
ℓ-uniform hypergraphsindependence numberSum-of-Squares (SoS) relaxationsemirandom modelspectral certificatestensor analysisrandom chaos matricesmatrix concentration inequalitiesplanted coloringpseudo-expectation
Authors
Pravesh Kothari, Anand Louis, Rameesh Paul, Prasad Raghavendra
Abstract
We study the problem of efficiently certifying upper bounds on the independence number of $\ell$-uniform hypergraphs. This is a notoriously hard problem, with efficient algorithms failing to approximate the independence number within $n^{1-ε}$ factor in the worst case [Has99, Zuc07]. We study the problem in random and semirandom hypergraphs. There is a folklore reduction to the graph case, achieving a certifiable bound of $O(\sqrt{n/p})$. More recently, the work [GKM22] improved this by constructing spectral certificates that yield a bound of $O(\sqrt{n}.\mathrm{polylog}(n)/p^{1/(\ell/2)})$. We make two key improvements: firstly, we prove sharper bounds that get rid of pesky logarithmic factors in $n$, and nearly attain the conjectured optimal (in both $n$ and $p$) computational threshold of $O(\sqrt{n}/p^{1/\ell})$, and secondly, we design robust Sum-of-Squares (SoS) certificates, proving our bounds in the more challenging semirandom hypergraph model. Our analysis employs the proofs-to-algorithms paradigm [BS16, FKP19] in showing an upper bound for pseudo-expectation of degree-$2\ell$ SoS relaxation of the natural polynomial system for maximum independent set. The challenging case is odd-arity hypergraphs, where we employ a tensor-based analysis that reduces the problem to proving bounds on a natural class of random chaos matrices associated with $\ell$-uniform hypergraphs. Previous bounds [AMP21, RT23] have a logarithmic dependence, which we remove by leveraging recent progress on matrix concentration inequalities [BBvH23, BLNvH25]; we believe these may be useful in other hypergraph problems. As an application, we show our improved certificates can be combined with an SoS relaxation of a natural $r$-coloring polynomial system to recover an arbitrary planted $r$-colorable subhypergraph in a semirandom model along the lines of [LPR25], which allows for strong adversaries.