Hierarchy Theorems for Property Testing

DOI10.1007/978-3-642-16367-8_22zbMath1309.68221OpenAlexW3091695494MaRDI QIDQ4933380

Michael Krivelevich, Oded Goldreich, Eyal Rozenberg, Ilan Newman

Publication date: 12 October 2010

Published in: Property Testing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.409

zbMATH Keywords

graph propertiesadaptivity versus non-adaptivitygraph blow-upmonotone graph propertiesone-sided versus two-sided error

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items

Hierarchy theorems for property testing, Optimal Testing of Reed-Muller Codes, Testing Graph Blow-Up, Introduction to Testing Graph Properties

Cites Work

• Unnamed Item
• Unnamed Item
• An analytic approach to stability
• Space complexity vs. query complexity
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• A sublinear bipartiteness tester for bounded degree graphs
• A combinatorial characterization of the testable graph properties
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Property testing and its connection to learning and approximation
• Testing graph isomorphism
• Every Monotone Graph Property Is Testable
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Simple Constructions of Almost k-wise Independent Random Variables
• Three theorems regarding testing graph properties
• Testing membership in parenthesis languages
• Robust Characterizations of Polynomials with Applications to Program Testing
• lgorithmic and Analysis Techniques in Property Testing
• Some 3CNF Properties Are Hard to Test
• Testing monotonicity
• Efficient testing of large graphs
• Property testing in bounded degree graphs