Hierarchy theorems for property testing

DOI10.1007/S00037-011-0022-4MaRDI QIDQ430844zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

Publication date 26 June 2012

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-011-0022-4

zbMATH Keywords

query complexityproperty testinghierarchy theoremsadaptivity versus non-adaptivitygraph blow-upgraph propertiesmonotone graph propertiesone-sided versus two-sided error

Mathematics Subject Classification ID

Randomized algorithms (68W20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Hierarchy theorems for property testing
• Hierarchy Theorems for Property Testing
• Hierarchy theorems for testing properties in size-oblivious query complexity
• An adaptivity hierarchy theorem for property testing
• An adaptivity hierarchy theorem for property testing

Cites work

• scientific article; zbMATH DE number 5485551 (Why is no real title available?)
• scientific article; zbMATH DE number 6469238 (Why is no real title available?)
• A combinatorial characterization of the testable graph properties, it's all about regularity
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A sublinear bipartiteness tester for bounded degree graphs
• Algorithmic and analysis techniques in property testing
• An analytic approach to stability
• Efficient testing of large graphs
• Every Monotone Graph Property Is Testable
• Graph limits and parameter testing
• Hierarchy theorems for property testing
• Inflatable graph properties and natural property tests
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Property testing. A learning theory perspective
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Simple Constructions of Almost k-wise Independent Random Variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Some 3CNF Properties Are Hard to Test
• Space complexity vs. query complexity
• Testing Graph Isomorphism
• Testing graph blow-up
• Testing membership in parenthesis languages
• Testing monotonicity
• Testing subgraphs in directed graphs
• Testing subgraphs in large graphs
• Three theorems regarding testing graph properties

Cited in

(7)

• Robustly self-ordered graphs: constructions and applications to property testing
• Every Set in P Is Strongly Testable Under a Suitable Encoding
• Some 3CNF properties are hard to test
• Testing hierarchical systems
• Hierarchy theorems for property testing
• Hierarchy theorems for testing properties in size-oblivious query complexity
• Hierarchy Theorems for Property Testing

This page was built for publication: Hierarchy theorems for property testing

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