A Caltech Library Service

A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers

Hurwitz, Jeremy (2011) A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers. In: Algorithms and Computation: 22nd International Symposium. Lecture Notes in Computer Science. No.7074. Springer , Berlin, pp. 524-533. ISBN 978-3-642-25590-8.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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=Θ~(q^(2−2/t)), where q=Θ~(ϵ⁻¹) is the adaptive query complexity. This resolves the question of how beneficial adaptivity is, in the context of proximity-dependent properties. This also gives evidence that the canonical transformation of Goldreich and Trevisan 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(εN) and being a blow-up collection of an arbitrary base graph H.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access Paper ItemMaster's thesis
Additional Information:© 2011 Springer-Verlag Berlin Heidelberg. Supported by NSF grants CCF-0830787, CCF-0829909, and CCF-1116111. Thank you to Oded Goldreich and Chris Umans for very helpful comments and discussions about early versions of this work.
Funding AgencyGrant Number
Subject Keywords:Sublinear-Time Algorithms; Property Testing; Dense-Graph Model; Adaptive vs Non-adaptive Queries; Hierarchy Theorem
Series Name:Lecture Notes in Computer Science
Issue or Number:7074
Record Number:CaltechAUTHORS:20200529-111433160
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:103574
Deposited By: Tony Diaz
Deposited On:29 May 2020 18:27
Last Modified:16 Nov 2021 18:22

Repository Staff Only: item control page