On the randomness complexity of property testing

DOI10.1007/S00037-009-0282-4zbMATH Open1204.68097OpenAlexW1989636021MaRDI QIDQ623502FDOQ623502

Authors: Oded Goldreich, Or Sheffet 

Publication date: 7 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-009-0282-4

Recommendations

• On the Randomness Complexity of Property Testing
• scientific article; zbMATH DE number 1241385
• A sublinear bipartiteness tester for bounded degree graphs
• scientific article; zbMATH DE number 1775414
• On the benefits of adaptivity in property testing of dense graphs

zbMATH Keywords

samplingproperty testingrandomness extractorsrandomness complexityweak sources of randomness

Mathematics Subject Classification ID

Randomized algorithms (68W20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (14)

• An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
• Erasure-Resilient Property Testing
• Non-interactive proofs of proximity
• On the power of relaxed local decoding algorithms
• A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
• On the Randomness Complexity of Property Testing
• Proofs of proximity for distribution testing
• An exponential separation between MA and AM proofs of proximity
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
• A test for randomness based on a complexity measure
• Finding cycles and trees in sublinear time
• On the average-case complexity of property testing
• Succinct interactive oracle proofs: applications and limitations
• White-box vs. black-box complexity of search problems: Ramsey and graph property testing

This page was built for publication: On the randomness complexity of property testing

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