On using deterministic functions to reduce randomness in probabilistic algorithms

DOI10.1016/0890-5401(87)90023-XzbMath0629.68047MaRDI QIDQ1094137

Miklos Santha

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

samplingrandomized algorithmserror probability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Simulating BPP using a general weak random source, Pseudorandom generators for space-bounded computation, Construction of expanders and superconcentrators using Kolmogorov complexity, Extractors from Reed-Muller codes, Realistic analysis of some randomized algorithms, On the second eigenvalue of hypergraphs, Randomness in interactive proofs

Cites Work

• Unnamed Item
• Expanders obtained from affine transformations
• On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
• A Remark on Stirling's Formula
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• A Simple Unpredictable Pseudo-Random Number Generator
• Better expanders and superconcentrators
• Superconcentrators