CaltechTHESIS
  A Caltech Library Service

A nearly-quadratic gap between adaptive and non-adaptive property testers

Citation

Hurwitz, Jeremy S. (2012) A nearly-quadratic gap between adaptive and non-adaptive property testers. Master's thesis, California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:11302011-091414252

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 non-adaptive query complexity $Q=\widetilde{\Theta}(q^{2-2/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 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 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 \cite{algorithmic-aspects}, Goldreich and Ron proved that when $H$ is a simple $t$-cycle, the non-adaptive 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 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(\epsilon N)$ requires only $O(\epsilon^{-1}\lg^3{\epsilon^{-1}})$ adaptive queries or $O(\epsilon^{-2+1/(\delta+2)}+\epsilon^{-2+2/W})$ non-adaptive 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: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
Author Email:jhurwitz (AT) cs.caltech.edu
Funders:
Funding AgencyGrant Number
NSFUNSPECIFIED
NSFUNSPECIFIED
Record Number:CaltechTHESIS:11302011-091414252
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:11302011-091414252
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

[img]
Preview
PDF (Master's Thesis) - Final Version
See Usage Policy.

627Kb

Repository Staff Only: item control page