Canonne, Clément L. ;
Gur, Tom
An Adaptivity Hierarchy Theorem for Property Testing
Abstract
Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of adaptive testing algorithms, wherein each query may be determined by the answers received to prior queries, and their nonadaptive counterparts, in which all queries are independent of answers obtained from previous queries.
In this work, we investigate the role of adaptivity in property testing at a finer level. We first quantify the degree of adaptivity of a testing algorithm by considering the number of "rounds of adaptivity" it uses. More accurately, we say that a tester is k(round) adaptive if it makes queries in k+1 rounds, where the queries in the i'th round may depend on the answers obtained in the previous i1 rounds. Then, we ask the following question:
Does the power of testing algorithms smoothly grow with the number of rounds of adaptivity?
We provide a positive answer to the foregoing question by proving an adaptivity hierarchy theorem for property testing. Specifically, our main result shows that for every n in N and 0 <= k <= n^{0.99} there exists a property Pi_{n,k} of functions for which (1) there exists a kadaptive tester for Pi_{n,k} with query complexity tilde O(k), yet (2) any (k1)adaptive tester for Pi_{n,k} must make Omega(n) queries. In addition, we show that such a qualitative adaptivity hierarchy can be witnessed for testing natural properties of graphs.
BibTeX  Entry
@InProceedings{canonne_et_al:LIPIcs:2017:7516,
author = {Cl{\'e}ment L. Canonne and Tom Gur},
title = {{An Adaptivity Hierarchy Theorem for Property Testing}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {27:127:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7516},
URN = {urn:nbn:de:0030drops75164},
doi = {10.4230/LIPIcs.CCC.2017.27},
annote = {Keywords: Property Testing, Coding Theory, Hierarchy Theorems}
}
2017
Keywords: 

Property Testing, Coding Theory, Hierarchy Theorems 
Seminar: 

32nd Computational Complexity Conference (CCC 2017)

Issue date: 

2017 
Date of publication: 

2017 