A Tolerant Independent Set Tester

Cameron Seth

We give nearly optimal bounds on the sample complexity of $(\tilde{\Omega }(\epsilon ),\epsilon )$-tolerant testing the $\rho$-independent set property in the dense graph setting. In particular, we give…