Princeton University

Computer Science 597E


This seminar course will focus on the recent developments in the theory of derandomization. We will focus on the intimate connection between the derandomization of probabilistic polynomialtime algorithms and complexitytheoretic lower bounds, as well as on some approaches to derandomization of specific problems of interest (e.g. primality testing, polynomial identity testing). The course will meet on Fridays, 1:303:30PM, in Room 302 (Room may change). Students enrolled in the course will each present one paper, and take one set of scribe notes on others' presentations. There will be no other formal requirements for students in the course. Papers we will cover will include (hopefully) most of the following:  M. Agrawal and S. Biswas. Primality and identity testing via chinese remaindering. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science, pages 202 209, 1999. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Preprint (http://www.cse.iitk.ac.in/users/manindra/primality.ps), August 2002. L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Complexity, 3:307 318, 1993. O. Goldreich, S. Vadhan, and A. Wigderson. Simplified derandomization of BPP using a hitting set generator. Electronic Colloquium on Computational Complexity, TR00004, 2000. R. Impagliazzo. Hardcore distributions for somewhat hard problems. In Proceedings of the ThirtySixth Annual IEEE Symposium on Foundations of Computer Science, pages 538 545, 1995. R. Impagliazzo, V. Kabanets, and A. Wigderson. In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences, 65(4):672 694, 2002. (preliminary version in CCC 01). R. Impagliazzo and A. Wigderson. P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In Proceedings of the TwentyNinth Annual ACM Sympo sium on Theory of Computing, pages 220 229, 1997. V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means prov ing circuit lower bounds. In Proceedings of the ThirtyFifth Annual ACM Symposium on Theory of Computing, pages 355 364, 2003. A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial hierarchy collapses. In Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, pages 659 667, 1999. N. Nisan and A. Wigderson. Hardness vs. randomness. Journal of Computer and System Sciences, 49:149 167, 1994. M. Sudan, L. Trevisan, and S. Vadhan. Pseudorandom generators without the XOR lemma. Journal of Computer and System Sciences, 62(2):236 266, 2001. (preliminary version in STOC 99). L. Trevisan. Construction of extractors using pseudorandom generators. In Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, pages 141 148, 1999. C. Umans. Pseudorandom generators for all hardnesses. In Proceedings of the Thirty Fourth Annual ACM Symposium on Theory of Computing, pages 127 134, 2002.
Professor: Amit Sahai  406 CS Building  2580255 sahai@cs.princeton.edu
Graduate Coordinator: Melissa Lawson  310 CS Building  2585387 mml@cs.princeton.edu
Teaching Assistants: TBA