Testing the Independent Set Property in Hypergraphs

Elena Grigorescu, Shreya Nasa, Cameron Seth

The optimal sample complexity of testing if an $n$-vertex graph has an independent set of size $\rho n$, or is $\epsilon$-far from having an independent set of size $\rho n$, was establ…