CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20200529-111433160

[img] PDF - Submitted Version
See Usage Policy.

521kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200529-111433160

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=Θ~(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
https://doi.org/10.1007/978-3-642-25591-5_54DOIArticle
https://rdcu.be/b4uQMPublisherFree ReadCube access
https://arxiv.org/abs/1102.5309arXivDiscussion Paper
https://resolver.caltech.edu/CaltechTHESIS:11302011-091414252Related 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.
Funders:
Funding AgencyGrant Number
NSFCCF-0830787
NSFCCF-0829909
NSFCCF-1116111
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:https://resolver.caltech.edu/CaltechAUTHORS:20200529-111433160
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:103574
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:29 May 2020 18:27
Last Modified:29 May 2020 18:27

Repository Staff Only: item control page