Hierarchy Theorems for Property Testing

DOI10.1007/978-3-642-03685-9_38MaRDI QIDQ3638900zbMATH OpenOpenAlexFDO

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

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_38

zbMATH Keywords

adaptivity vs non-adaptivitygraph blow-upgraph propertiesmonotone graph propertiesone-sided vs two-sided errorproperty testing

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
• An adaptivity hierarchy theorem for property testing

Cited in

(8)

• Hierarchy theorems for testing properties in size-oblivious query complexity
• Testing hierarchical systems
• Inflatable graph properties and natural property tests
• Some 3CNF properties are hard to test
• Hierarchy theorems for property testing
• Hierarchy theorems for property testing
• Testing graph blow-up
• An analytic approach to stability

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