Citation
Hurwitz, Jeremy S. (2012) A nearlyquadratic gap between adaptive and nonadaptive property testers. Master's thesis, California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:11302011091414252
Abstract
We show that for all integers $t\geq 8$ and arbitrarily small $\epsilon>0$, there exists a graph property $\Pi$ (which depends on $\epsilon$) such that $\epsilon$testing $\Pi$ has nonadaptive query complexity $Q=\widetilde{\Theta}(q^{22/t})$, where $q=\widetilde{O}(\epsilon^{1})$ is the adaptive query complexity. This resolves the question of how beneficial adaptivity is, in the context of proximitydependent properties (\cite{benefitsofadaptivity}). This also gives evidence that the canonical transformation of Goldreich and Trevisan (\cite{canonicaltesters}) is essentially optimal when converting an adaptive property tester into a nonadaptive 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) blowup of a given basegraph $H$. In \cite{algorithmicaspects}, Goldreich and Ron proved that when $H$ is a simple $t$cycle, the nonadaptive query complexity is $\Omega(\epsilon^{2+2/t})$, even under the promise that $G$ has maximum degree $O(\epsilon N)$. In this thesis, we prove a matching upper bound for the nonadaptive 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 blowups of $H$ and has maximum degree $O(\epsilon N)$ requires only $O(\epsilon^{1}\lg^3{\epsilon^{1}})$ adaptive queries or $O(\epsilon^{2+1/(\delta+2)}+\epsilon^{2+2/W})$ nonadaptive queries, where $\delta=\Delta(H)$ is the maximum degree of $H$ and $W≺\abs{H}^2$ is a bound on the size of witnesses against $H$.
Item Type:  Thesis (Master's thesis)  

Subject Keywords:  SublinearTime Algorithms, Property Testing, DenseGraph Model, Adaptive vs Nonadaptive 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): 
 
Thesis Committee: 
 
Defense Date:  December 2011  
Author Email:  jhurwitz (AT) cs.caltech.edu  
Funders: 
 
Record Number:  CaltechTHESIS:11302011091414252  
Persistent URL:  http://resolver.caltech.edu/CaltechTHESIS:11302011091414252  
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  6741  
Collection:  CaltechTHESIS  
Deposited By:  Jeremy Hurwitz  
Deposited On:  06 Jan 2012 22:42  
Last Modified:  26 Dec 2012 04:39 
Thesis Files

PDF (Master's Thesis)
 Final Version
See Usage Policy. 627Kb 
Repository Staff Only: item control page