Reproduce “Improved Certificates for Independence Number in Semirandom Hypergraphs” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Pravesh Kothari, Anand Louis, Rameesh Paul, Prasad Raghavendra
The authors develop Sum-of-Squares certificates that upper-bound the size of a maximum independent set in random hypergraphs without finding it. Boolean membership constraints make the analysis track candidate-set size, and the certificates remain valid after an adversary adds edges. For even arity six and edge probability one-half, it certifies an upper bound of O_6(√n) with high probability, in n^{O(6)} time.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.