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

Abstract. We show that for all integers t ≥ 8 and arbitrarily small > 0, there exists a graph property Π (which depends on ) such that -testing Π has non-adaptive query complexity Q = Θ̃(q2−2/t), where q = Θ̃(−1) is the adaptive query complexity. This resolves the question of how beneficial adaptivity is, in the context of proximity-dependent properties ([9]). This also gives evidence that the canonical transforma-tion of Goldreich and Trevisan ([8]) is essentially optimal when convert-ing 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(N) and being a blow-up collection of an arbitrary base graph H