Hierarchy Theorems for Property Testing

DOI10.1007/978-3-642-03685-9_38zbMath1255.68290OpenAlexW2171582965MaRDI QIDQ3638900

Ilan Newman, Eyal Rozenberg, Oded Goldreich, Michael Krivelevich

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

graph propertiesproperty testinggraph blow-upmonotone graph propertiesadaptivity vs non-adaptivityone-sided vs 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 (3)

An analytic approach to stability ⋮ Testing Graph Blow-Up ⋮ Inflatable Graph Properties and Natural Property Tests

This page was built for publication: Hierarchy Theorems for Property Testing