HARD VS RANDOM

This is a collection of papers/surveys/writeups on the premise that

IF there exists hard problems THEN P=R.

1. Hardness vs. Randomness by Nisan and Wigderson. JCSS Vol 49, No. 2, pages 149-167, 1994 NW.

2. Write up of parts of Hardness vs. Randomness by William Gasarch. WRITEUPNW.

3. Simplified Derandomization of BPP using a Hitting Set Geneator by Oded Goldreich, Salil Vadhan, and Avi Wigderson. HIT.

4. Derandomization: A Brief Overview by Valentine Kabanets. Bulletin of the European Association of Theoretical Computer Science, Number 76, pages 88-103, 2002. KAB.

5. BPP has Subexponential Time Simulations unless EXPTIME has publishable proofs by Babai, Fortnow, Nisan, and Wigderson. Complexity Vol 3, pages 307-318, 1993. BFNW.

6. On Yao's XOR Lemma by Oded Goldreich, Noam Nisan, and Ave Wigderson. Electronic Colloiquim on Computational Complexity, TR95-050, 1995. (This is revised version from Goldreich website.) YAOXOR.

7. $P=BPP$ if $E$ Requires Exponetial Circuits: Derandomizing the XOR Lemma by Russell Impagliazoo and Avi Wigderson. From 29th FOCS, 1997. IW.

8. List Decoding: Algorithms and Applications by Madhu Sudan. SIGACT NEWS Complexity Theory Column 25, 2001. LISTDECODING.

9. Derandomizing Complexity Classes by Peter Bro Milterson. Book chapter in Handbook of Randomized Computing MILT.

10. One-way functions and psuedo-random generators by Marius Zimand. Book Chapter in forthcoming book Computational Complexity: A Quantitative Perspective ZIM.

11. Pseudo-random generators for all hardnesses by Christopher Umans. JCSS Vol 67, 2003 UMANS.