On the randomness complexity of property testing

DOI10.1007/S00037-009-0282-4MaRDI QIDQ623502zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(14)

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

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)