Preliminary versionA preliminary version of these results was presented in: Michael Saks, Aravind Srinivasan, and Shiyu Zhou. Explicit dispersers with polylog degree. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 479-488, Las Vegas, Nevada, 29 May-1 June 1995.
Categories and Subject Descriptors: F.1.3 [Computation by Abstract Devices]: Complexity Classes -- relations among randomized complexity classes; G.2.1 [Discrete Mathematics]: Combinatorics -- combinatorial algorithms; G.3 [Probability and Statistics] -- probabilistic algorithms
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Derandomization, expander graphs, explicit constructions, hashing lemmas, hardness of approximation, imperfect sources of randomness, measures of information, pseudo-random generators, randomized computation, time-space tradeoffs
Selected papers that cite this one
- Alexander E. Andreev, Andrea E. F. Clementi, and José D. P. Rolim. A new general derandomization method. Journal of the ACM, 45(1):179-213, January 1998.
Selected references
- 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, and José D. P. Rolim. A new general derandomization method. Journal of the ACM, 45(1):179-213, January 1998.
- 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.
- 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.
- Aviad Cohen and Avi Wigderson. Dispersers, deterministic amplification, and weak random sources (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 14-19, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
- Amos Fiat and Moni Naor. Implicit O(1) probe search. SIAM Journal on Computing, 22(1):1-10, February 1993.
- Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 220-229, El Paso, Texas, 4-6 May 1997.
- Russell Impagliazzo and David Zuckerman. How to recycle random bits. In 30th Annual Symposium on Foundations of Computer Science, pages 248-253, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
- 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.
- Miklos Santha. On using deterministic functions to reduce randomness in probabilistic algorithms. Information and Computation, 74(3):241-249, September 1987.
- Miklos Santha and Umesh V. Vazirani. Generating quasi-random sequences from semi-random sources. Journal of Computer and System Sciences, 33(1):75-87, August 1986.
- Michael Sipser. Expanders, randomness, or time versus space. Journal of Computer and System Sciences, 36(3):379-383, June 1988.
- Aravind Srinivasan and David Zuckerman. Computing with very weak random sources. In 35th Annual Symposium on Foundations of Computer Science, pages 264-275, Santa Fe, New Mexico, 20-22 November 1994. IEEE.
- 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.
- Umesh V. Vazirani and Vijay V. Vazirani. Random polynomial time is equal to slightly-random polynomial time. In 26th Annual Symposium on Foundations of Computer Science, pages 417-428, Portland, Oregon, 21-23 October 1985. IEEE.
- Avi Wigderson and David Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 245-251, San Diego, California, 16-18 May 1993.
- David Zuckerman. General weak random sources. In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 534-543, St. Louis, Missouri, 22-24 October 1990. IEEE.
- David Zuckerman. Simulating BPP using a general weak random source. In 32nd Annual Symposium on Foundations of Computer Science, pages 79-89, San Juan, Puerto Rico, 1-4 October 1991. IEEE.
- David Zuckerman. NP-complete problems have a version that's hard to approximate. In Proceedings of the Eighth Annual Structure in Complexity Theory Conference, pages 305-312, San Diego, California, 18-21 May 1993. IEEE Computer Society Press.
- David Zuckerman. Randomness-optimal sampling, extractors, and constructive leader election. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 286-295, Philadelphia, Pennsylvania, 22-24 May 1996.