Student Presentations.

The last third of the course will cover current research. Please pick a paper or
group of papers to present in class. I will assist you in understanding the
papers and preparing your presentation.

1. Hardness v/s Randomness. (Possibly a 2-person project.)
   (i) "Hardness v/s Randomness" by Nisan and Wigderson. JCSS 149--167, 1994.
   (Prelim. version in ACM STOC 1988.)
   (ii) "Pseudorandom Generators Without the XOR Lemma."
      Madhu Sudan, Luca Trevisan and Salil Vadhan. STOC'99.
2. "Construction of Extractors Using Pseudorandom Generators" by Luca Trevisan. STOC'99.
3. Nondeterministic polynomial time versus nondeterministic logartithmic space:
   Time-space tradeoffs for satisfiability. Lance Fortnow, Structures'97.
4. Which Problems Have Strongly Exponential Complexity? by Impagliazzo, Paturi, and Zane. FOCS'98.
5. Lowerbounds for propositional proof systems. (Possibly a 2-person project.)
   (i) Simplified and Improved Resolution Lower Bounds by Beame and Pittasi. FOCS'98.
   (ii) Exponential lower bounds for bounded depth Frege proofs of Pigeonhole Principle. Survey by P. Beame.