A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers

Jeremy Hurwitz

We show that for all integers $t\ge 8$ and arbitrarily small $\epsilon >0$, there exists a graph property $\Pi$ (which depends on $\epsilon$) such that $\epsilon$-testing $\Pi$ has non-adaptive query compl…