Preliminary versionA preliminary version of these results was presented in: Alexander E. Andreev, Andrea E. F. Clementi, and José D. P. Rolim. Hitting sets derandomize BPP. In Friedhelm Meyer auf der Heide and Burkhard Monien, editors, Automata, Languages and Programming, 23rd International Colloquium, volume 1099 of Lecture Notes in Computer Science, pages 357-368, Paderborn, Germany, 8-12 July 1996. Springer-Verlag.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.3 [Probability and Statistics] -- probabilistic algorithms
General Terms: Algorithms, Theory
Additional Key Words and Phrases: BPP, Boolean circuits, derandomization
Selected papers that cite this one
- Michael Saks, Aravind Srinivasan, and Shiyu Zhou. Explicit OR-dispersers with polylogarithmic degree. Journal of the ACM, 45(1):123-154, January 1998.
Selected references
- Alexander E. Andreev, Andrea E. F. Clementi, and José D. P. Rolim. Efficient construction of hitting sets for systems of linear functions. In 14th Annual Symposium on Theoretical Aspects of Computer Science, volume 1200 of Lecture Notes in Computer Science, pages 387-398, Lübeck, Germany, 27 February-mar 1 1997. Springer.
- Alexander E. Andreev, Andrea E. F. Clementi, and José D. P. Rolim. Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs. In Pierpaolo Degano and Robert Gorrieri and Alberto Marchetti-Spaccamela, editors, Automata, Languages and Programming, 24th International Colloquium, volume 1256 of Lecture Notes in Computer Science, pages 177-187, Bologna, Italy, 7-11 July 1997. Springer-Verlag.
- Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, and Luca Trevisan. Weak random sources, hitting sets, and BPP simulations. In 38th Annual Symposium on Foundations of Computer Science, pages 264-272, Miami Beach, Florida, 20-22 October 1997. IEEE.
- Mihir Bellare and John Rompel. Randomness-efficient oblivious sampling. In 35th Annual Symposium on Foundations of Computer Science, pages 276-287, Santa Fe, New Mexico, 20-22 November 1994. IEEE.
- Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13(4):850-864, November 1984.
- Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230-261, April 1988.
- Noam Nisan. Extracting randomness: How and why: A survey. In Proceedings, Eleventh Annual IEEE Conference on Computational Complexity, pages 44-58, Philadelphia, Pennsylvania, 24-27 May 1996. IEEE Computer Society Press.
- Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of Computer and System Sciences, 49(2):149-167, October 1994.
- Michael Saks, Aravind Srinivasan, and Shiyu Zhou. Explicit OR-dispersers with polylogarithmic degree. Journal of the ACM, 45(1):123-154, January 1998.
- Amnon Ta-Shma. On extracting randomness from weak random sources (extended abstract). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 276-285, Philadelphia, Pennsylvania, 22-24 May 1996.
- Andrew C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 80-91, Chicago, Illinois, 3-5 November 1982. IEEE.