Another Motivation for Reducing the Randomness Complexity of Algorithms

DOI10.1007/978-3-642-22670-0_36zbMath1291.68430OpenAlexW2155494727MaRDI QIDQ3088202

Oded Goldreich

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_36

zbMATH Keywords

samplingpseudorandom generatorsproperty testingrandomness extractorsrandomness complexityweak sources of randomness

Mathematics Subject Classification ID

Computational methods for problems pertaining to probability theory (60-08) Randomized algorithms (68W20) Sampling theory in information and communication theory (94A20)

Cites Work

• Unnamed Item
• Unnamed Item
• Randomness in interactive proofs
• A sublinear bipartiteness tester for bounded degree graphs
• Extractors from Reed-Muller codes
• A Brief Introduction to Property Testing
• Property testing and its connection to learning and approximation
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• On the Randomness Complexity of Property Testing
• Foundations of Cryptography
• Robust Characterizations of Polynomials with Applications to Program Testing
• lgorithmic and Analysis Techniques in Property Testing
• Property testing in bounded degree graphs