Improved Certificates for Independence Number in Semirandom Hypergraphs

Pravesh Kothari, Anand Louis, Rameesh Paul +1

We study the problem of efficiently certifying upper bounds on independence number of $\ell$-uniform hypergraphs in semirandom models. This is a notoriously hard problem, with effi…