Hierarchy theorems for property testing

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

zbMATH Keywords

graph propertiesproperty testingquery complexityhierarchy theoremsadaptivity versus non-adaptivitygraph blow-upmonotone graph propertiesone-sided versus two-sided error

Mathematics Subject Classification ID

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