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

Abstract

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 complexity $Q=\tilde{\Theta }(q^{2-2/t})$, where $q=\tilde{\Theta }({\epsilon }^{-1})$ is the adaptive query complexity. This resolves the question of how beneficial adaptivity is, in the context of proximity-dependent properties (\cite{benefits-of-adaptivity}). This also gives evidence that the canonical transformation of Goldreich and Trevisan (\cite{canonical-testers}) is essentially optimal when converting an adaptive property tester to a non-adaptive property tester. To do so, we provide optimal adaptive and non-adaptive testers for the combined property of having maximum degree $O(\epsilon N)$ and being a \emph{blow-up collection} of an arbitrary base graph $H$.

Keywords: Sublinear-Time Algorithms, Property Testing, Dense-Graph Model, Adaptive vs Nonadaptive Queries, Hierarchy Theorem