On the Randomness Complexity of Property Testing

DOI10.1007/978-3-540-74208-1_37MaRDI QIDQ3603490zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Or Sheffet

Publication date 17 February 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74208-1_37

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

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

(8)

• On the average-case complexity of property testing
• Another motivation for reducing the randomness complexity of algorithms
• Distribution-Free Property-Testing
• A test for randomness based on a complexity measure
• Erasure-Resilient Property Testing
• Invariance in property testing
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
• On the randomness complexity of 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 Q3603490)