On the Randomness Complexity of Property Testing

DOI10.1007/978-3-540-74208-1_37zbMath1171.68727OpenAlexW1513180873MaRDI QIDQ3603490

Or Sheffet, Oded Goldreich

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) Graph theory (including graph drawing) in computer science (68R10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Invariance in Property Testing ⋮ Another Motivation for Reducing the Randomness Complexity of Algorithms

This page was built for publication: On the Randomness Complexity of Property Testing