Another Motivation for Reducing the Randomness Complexity of Algorithms
From MaRDI portal
Publication:3088202
DOI10.1007/978-3-642-22670-0_36zbMath1291.68430OpenAlexW2155494727MaRDI QIDQ3088202
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
samplingpseudorandom generatorsproperty testingrandomness extractorsrandomness complexityweak sources of randomness
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