Another motivation for reducing the randomness complexity of algorithms

DOI10.1007/978-3-642-22670-0_36MaRDI QIDQ3088202zbMATH OpenOpenAlexFDO

Authors 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

property testingpseudorandom generatorsrandomness complexityrandomness extractorssamplingweak 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)

Recommendations

• Randomness is linear in space
• Computing with Very Weak Random Sources
• scientific article; zbMATH DE number 6963652
• scientific article; zbMATH DE number 1857655
• Randomness extractors -- applications and constructions

Cites work

• A Brief Introduction to Property Testing
• A sublinear bipartiteness tester for bounded degree graphs
• Algorithmic and analysis techniques in property testing
• Extractors from Reed-Muller codes
• Foundations of Cryptography
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• scientific article; zbMATH DE number 1820017 (Why is no real title available?)
• scientific article; zbMATH DE number 3960854 (Why is no real title available?)
• On the Randomness Complexity of Property Testing
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Randomness in interactive proofs
• Robust Characterizations of Polynomials with Applications to Program Testing

This page was built for publication: Another motivation for reducing the randomness complexity of algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088202)