Hierarchy theorems for property testing
From MaRDI portal
Publication:430844
DOI10.1007/s00037-011-0022-4zbMath1282.68114OpenAlexW1968752573MaRDI QIDQ430844
Ilan Newman, Michael Krivelevich, Eyal Rozenberg, Oded Goldreich
Publication date: 26 June 2012
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-011-0022-4
graph propertiesproperty testingquery complexityhierarchy theoremsadaptivity versus non-adaptivitygraph blow-upmonotone graph propertiesone-sided versus two-sided error
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
Related Items
Hierarchy theorems for testing properties in size-oblivious query complexity, Every Set in P Is Strongly Testable Under a Suitable Encoding
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An analytic approach to stability
- Space complexity vs. query complexity
- Self-testing/correcting with applications to numerical problems
- A sublinear bipartiteness tester for bounded degree graphs
- A combinatorial characterization of the testable graph properties
- Graph limits and parameter testing
- Inflatable Graph Properties and Natural Property Tests
- 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 subgraphs in large graphs
- Testing membership in parenthesis languages
- Robust Characterizations of Polynomials with Applications to Program Testing
- Hierarchy Theorems for Property Testing
- lgorithmic and Analysis Techniques in Property Testing
- Some 3CNF Properties Are Hard to Test
- Testing Graph Blow-Up
- Testing subgraphs in directed graphs
- Testing monotonicity
- Efficient testing of large graphs
- Property testing in bounded degree graphs
