On the average-case complexity of property testing

DOI10.1007/978-3-642-22670-0_15MaRDI QIDQ3088183zbMATH OpenOpenAlexFDO

Authors Oded Goldreich

Publication date 19 August 2011

Published in Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22670-0_15

zbMATH Keywords

average-case complexityproperty testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• On the randomness complexity of property testing
• On the Randomness Complexity of Property Testing
• Distribution-free property testing
• Distribution-Free Property-Testing
• Property testing lower bounds via communication complexity

Cites work

• A Brief Introduction to Property Testing
• A sublinear bipartiteness tester for bounded degree graphs
• Algebraic property testing: the role of invariance
• Algorithmic and analysis techniques in property testing
• scientific article; zbMATH DE number 2019636 (Why is no real title available?)
• scientific article; zbMATH DE number 1775411 (Why is no real title available?)
• On the randomness complexity of property testing
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Proximity oblivious testing and the role of invariances
• Quick approximation to matrices and applications
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing monotonicity
• Testing subgraphs in large graphs
• The complexity of promise problems with applications to public-key cryptography
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Three theorems regarding testing graph properties

Cited in

(3)

• Lower bounds for approximating graph parameters via communication complexity
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
• Abstract Combinatorial Programs and Efficient Property Testers

This page was built for publication: On the average-case complexity of property testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088183)