On the Average-Case Complexity of Property Testing
From MaRDI portal
Publication:3088183
DOI10.1007/978-3-642-22670-0_15zbMath1343.68296OpenAlexW1509004471MaRDI QIDQ3088183
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
Related Items
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