Hierarchy theorems for property testing

DOI10.1007/978-3-642-16367-8_22MaRDI QIDQ4933380zbMATH OpenOpenAlexFDO

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

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

adaptivity versus non-adaptivitygraph blow-upgraph propertiesmonotone graph propertiesone-sided versus two-sided error

Mathematics Subject Classification ID

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

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
• Three theorems regarding testing graph properties

Cites work

• 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
• scientific article; zbMATH DE number 1820017 (Why is no real title available?)
• scientific article; zbMATH DE number 5485551 (Why is no real title available?)
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• 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
• Spot-checkers
• Testing graph isomorphism
• Testing membership in parenthesis languages
• Testing monotonicity
• Three theorems regarding testing graph properties

Cited in

(8)

• Hierarchy theorems for testing properties in size-oblivious query complexity
• Testing hierarchical systems
• Introduction to testing graph properties
• Some 3CNF properties are hard to test
• Hierarchy Theorems for Property Testing
• Hierarchy theorems for property testing
• Optimal testing of Reed-Muller codes
• Testing graph blow-up

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 Q4933380)