A Brief Introduction to Property Testing

DOI10.1007/978-3-642-22670-0_31MaRDI QIDQ3088197zbMATH 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_31

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Cites work

• A combinatorial characterization of the testable graph properties, it's all about regularity
• A sublinear bipartiteness tester for bounded degree graphs
• Algorithmic and analysis techniques in property testing
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Introduction to testing graph properties
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Property testing of massively parametrized problems -- a survey
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Tolerant property testing and distance approximation

Cited in

(7)

• New techniques and tighter bounds for local computation algorithms
• On the average-case complexity of property testing
• Randomness and computation
• Another motivation for reducing the randomness complexity of algorithms
• scientific article; zbMATH DE number 1857651 (Why is no real title available?)
• Local computation algorithms for spanners
• Erasures versus errors in local decoding and property testing

This page was built for publication: A Brief Introduction to Property Testing

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