Hierarchy Theorems for Property Testing
From MaRDI portal
Publication:4933380
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
graph propertiesadaptivity versus non-adaptivitygraph blow-upmonotone graph propertiesone-sided versus two-sided error
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