An adaptivity hierarchy theorem for property testing

DOI10.1007/s00037-018-0168-4zbMath1403.68331arXiv1702.05678OpenAlexW2594013878WikidataQ129780464 ScholiaQ129780464MaRDI QIDQ1630385

Clément 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

zbMATH Keywords

complexity theoryproperty testingsublinear-time algorithms

Mathematics Subject Classification ID

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

Related Items (9)

Algorithms that access the input via queries ⋮ Unnamed Item ⋮ Round-competitive algorithms for uncertainty problems with parallel queries ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ Unnamed Item ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity ⋮ The power of adaptivity in source identification with time queries on the path

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Property testing lower bounds via communication complexity
• Property testing. Current research and surveys
• Testing computability by width-two OBDDs
• Self-testing/correcting with applications to numerical problems
• Complexity measures and decision tree complexity: a survey.
• Exponentially improved algorithms and lower bounds for testing signed majorities
• Lower Bounds for Testing Computability by Small Width OBDDs
• On Testing Expansion in Bounded-Degree Graphs
• Property testing and its connection to learning and approximation
• Tight Bounds for Testing k-Linearity
• Improved Bounds for Testing Juntas
• Testing ±1-weight halfspace
• Rounds in Communication Complexity Revisited
• Three theorems regarding testing graph properties
• A Hierarchy Theorem for Interactive Proofs of Proximity
• Communication Complexity
• Robust Characterizations of Polynomials with Applications to Program Testing
• Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees
• Testing juntas nearly optimally
• lgorithmic and Analysis Techniques in Property Testing
• Introduction to Property Testing
• On the Power of Adaptivity in Sparse Recovery
• Some 3CNF Properties Are Hard to Test
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Efficient testing of large graphs

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