An adaptivity hierarchy theorem for property testing

DOI10.1007/S00037-018-0168-4MaRDI QIDQ1630385zbMATH OpenOpenAlexWikidataFDO

Authors Clement L. Canonne, Tom Gur

Publication date 10 December 2018

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.05678, https://drops.dagstuhl.de/opus/volltexte/2017/7516/

zbMATH Keywords

complexity theoryproperty testingsublinear-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

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 emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their emph{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 $ninmathbbN$ and $0lekle{n}^{0.99}$ there exists a property $mathcal{P}_{n,k}$ of functions for which (1) there exists a $k$-adaptive tester for $mathcal{P}_{n,k}$ with query complexity $ildeO(k)$, yet (2) any $(k-1)$-adaptive tester for $mathcal{P}_{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.

Recommendations

• An adaptivity hierarchy theorem for property testing
• On the benefits of adaptivity in property testing of dense graphs
• A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• Algorithmic Aspects of Property Testing in the Dense Graphs Model

Cites work

• A hierarchy theorem for interactive proofs of proximity
• Adaptivity helps for testing juntas
• Algorithmic and analysis techniques in property testing
• Algorithmic aspects of property testing in the dense graphs model
• An adaptivity hierarchy theorem for property testing
• Communication Complexity
• Complexity measures and decision tree complexity: a survey.
• Efficient testing of large graphs
• Exponentially improved algorithms and lower bounds for testing signed majorities
• scientific article; zbMATH DE number 5485587 (Why is no real title available?)
• scientific article; zbMATH DE number 6292744 (Why is no real title available?)
• Improved Bounds for Testing Juntas
• Introduction to Property Testing
• Lower Bounds for Testing Computability by Small Width OBDDs
• On testing expansion in bounded-degree graphs
• On the Power of Adaptivity in Sparse Recovery
• Property testing and its connection to learning and approximation
• Property testing bounds for linear and quadratic functions via parity decision trees
• Property testing lower bounds via communication complexity
• Property testing. A learning theory perspective
• Property testing. Current research and surveys
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Rounds in Communication Complexity Revisited
• Self-testing/correcting with applications to numerical problems
• Settling the query complexity of non-adaptive junta testing
• Some 3CNF Properties Are Hard to Test
• Strong locally testable codes with relaxed local decoders
• Testing computability by width-two OBDDs
• Testing juntas nearly optimally
• Testing ±1-weight halfspace
• Three theorems regarding testing graph properties
• Tight bounds for testing k-linearity

Cited in

(19)

• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• The power of adaptivity in source identification with time queries on the path
• Hierarchy theorems for testing properties in size-oblivious query complexity
• Round-competitive algorithms for uncertainty problems with parallel queries
• A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers
• Hierarchy Theorems for Property Testing
• Hierarchy theorems for property testing
• Erasure-Resilient Property Testing
• On the power of relaxed local decoding algorithms
• An adaptivity hierarchy theorem for property testing
• Optimal unateness testers for real-valued functions: Adaptivity helps
• Relaxed locally correctable codes
• Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
• Asymptotically-good RLCCs with \((\log n)^{2+o(1)}\) queries
• Non-adaptive edge counting and sampling via bipartite independent set queries
• Round-competitive algorithms for uncertainty problems with parallel queries
• Algorithms that access the input via queries

This page was built for publication: An adaptivity hierarchy theorem for property testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1630385)