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 polynomial-time algorithms and complexity-theoretic 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:30-3: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 Pro-ceedings 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, TR00-004, 2000. R. Impagliazzo. Hard-core distributions for somewhat hard problems. In Proceedings of the Thirty-Sixth 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 Twenty-Ninth 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 Thirty-Fifth 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 Thirty-First 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 Thirty-First Annual ACM Symposium on Theory of Computing, pages 141 148, 1999. C. Umans. Pseudo-random 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 - 258-0255 sahai@cs.princeton.edu
Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu
Teaching Assistants: TBA