On the Average-Case Complexity of Property Testing

DOI10.1007/978-3-642-22670-0_15zbMath1343.68296OpenAlexW1509004471MaRDI QIDQ3088183

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

property testingaverage-case complexity

Mathematics Subject Classification ID

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

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the randomness complexity of property testing
• Quick approximation to matrices and applications
• A sublinear bipartiteness tester for bounded degree graphs
• A Brief Introduction to Property Testing
• Property testing and its connection to learning and approximation
• The complexity of promise problems with applications to public-key cryptography
• Three theorems regarding testing graph properties
• Testing subgraphs in large graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• lgorithmic and Analysis Techniques in Property Testing
• Proximity Oblivious Testing and the Role of Invariances
• Testing monotonicity
• Property testing in bounded degree graphs