Weak random sources, hitting sets, and BPP simulations
- 23 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 16 (02725428) , 264-272
- https://doi.org/10.1109/sfcs.1997.646115
Abstract
We show how to simulate any BPP algorithm in polynomial time using a weak random source of min-entropy r/sup /spl gamma// for any /spl gamma/>0. This follows from a more general result about sampling with weak random sources. Our result matches an information-theoretic lower bound and solves a question that has been open for some years. The previous best results were a polynomial time simulation of RP (Saks et al., 1995) and a n(log/sup (k)/n)-time simulation of BPP for fixed k (Ta-Shma, 1996). Departing significantly from previous related works, we do not use extractors; instead we use the OR-disperser of (Saks et al., 1995) in combination with a tricky use of hitting sets borrowed from Andreev et al. (1996). Of independent interest is our new (simplified) proof of the main result of Andreev et al., (1996). Our proof also gives some new hardness/randomness trade-offs for parallel classes.Keywords
This publication has 15 references indexed in Scilit:
- Randomness-efficient oblivious samplingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Computing with very weak random sourcesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offsPublished by Springer Nature ,1997
- Simulating BPP using a general weak random sourceAlgorithmica, 1996
- Randomness is Linear in SpaceJournal of Computer and System Sciences, 1996
- Randomness-optimal sampling, extractors, and constructive leader electionPublished by Association for Computing Machinery (ACM) ,1996
- Hardness vs randomnessJournal of Computer and System Sciences, 1994
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication ComplexitySIAM Journal on Computing, 1988
- Efficiency considerations in using semi-random sourcesPublished by Association for Computing Machinery (ACM) ,1987
- Generating quasi-random sequences from semi-random sourcesJournal of Computer and System Sciences, 1986