The Library
An adaptivity hierarchy theorem for property testing
Tools
Canonne, Clément L. and Gur, Tom (2017) An adaptivity hierarchy theorem for property testing. In: 32nd Computational Complexity Conference (CCC 2017). Published in: 32nd Computational Complexity Conference (CCC 2017, 79 27:1-27:25. ISBN 9783959770408. doi:10.4230/LIPIcs.CCC.2017.27 ISSN 1868-8969.
|
PDF
WRAP-adaptivity-hierarchy-therorem-property-testing-Gur-2017.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (679Kb) | Preview |
Official URL: http://drops.dagstuhl.de/opus/volltexte/2017/7516
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 non-adaptive 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 i-1 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 k-adaptive tester for Pi_{n,k} with query complexity tilde O(k), yet (2) any (k-1)-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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Coding theory, Algorithms | ||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||
Journal or Publication Title: | 32nd Computational Complexity Conference (CCC 2017 | ||||
Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||
Place of Publication: | Dagstuhl, Germany | ||||
ISBN: | 9783959770408 | ||||
ISSN: | 1868-8969 | ||||
Official Date: | 21 July 2017 | ||||
Dates: |
|
||||
Volume: | 79 | ||||
Page Range: | 27:1-27:25 | ||||
DOI: | 10.4230/LIPIcs.CCC.2017.27 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Date of first compliant deposit: | 11 April 2019 | ||||
Date of first compliant Open Access: | 11 April 2019 | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 32nd Computational Complexity Conference (CCC 2017) | ||||
Type of Event: | Conference |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year