A Caltech Library Service

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


Hurwitz, Jeremy Scott (2012) A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers. Master's thesis, California Institute of Technology. doi:10.7907/W178-HP57.


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 ([GR07]). This also gives evidence that the canonical transformation of Goldreich and Trevisan ([GT03]) is essentially optimal when converting an adaptive property tester into a non-adaptive property tester.

To do so, we consider the property of being decomposable into a disjoint union of subgraphs, each of which is a (possibly unbalanced) blow-up of a given base-graph H. In [GR09], Goldreich and Ron proved that when H is a simple t-cycle, the non-adaptive query complexity is Ω(ε-2+2/t, even under the promise that G has maximum degree O(εN). In this thesis, we prove a matching upper bound for the non-adaptive complexity and a tight (up to a polylogarithmic factor) upper bound on the adaptive complexity.

Specifically, we show that for all H, testing whether G is a collection of blow-ups of H and has maximum degree O(εN) requires only O(ε-1lg3ε-1) adaptive queries or O(ε-2+1/(δ+2)-2+2/W) non-adaptive queries, where δ = Δ(H) is the maximum degree of H and W< |H|2 is a bound on the size of witnesses against H.

Item Type:Thesis (Master's thesis)
Subject Keywords:Sublinear-Time Algorithms, Property Testing, Dense-Graph Model, Adaptive vs Non-adaptive Queries, Hierarchy Theorem
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Umans, Christopher M. (co-advisor)
  • Schulman, Leonard J. (co-advisor)
Thesis Committee:
  • Unknown, Unknown
Defense Date:December 2011
Funding AgencyGrant Number
Record Number:CaltechTHESIS:11302011-091414252
Persistent URL:
Related URLs:
URLURL TypeDescription ItemBook Chapter
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6741
Deposited By: Jeremy Hurwitz
Deposited On:06 Jan 2012 22:42
Last Modified:29 May 2020 18:17

Thesis Files

PDF (Master's Thesis) - Final Version
See Usage Policy.


Repository Staff Only: item control page