Testing Graph Properties with the Container Method

Eric Blais, Cameron Seth

We establish nearly optimal sample complexity bounds for testing the $\ddot{I}$-clique property in the dense graph model. Specifically, we show that it is possible to distinguish graphs…