For your final project, you are expected to read one or several papers related to a complexity theory topic of your choice. You will be required to

- Write a short survey on the topic, about 5-7 pages long, to be submitted by Jan 10 and
- Give a 25 minute presentation about it in the last week of the class (Jan 3-Jan 8). You can either use slides or the whiteboard.

You can work either individually or in pairs. There is a list of topics suggested below, but you should not feel obliged to choose from the list. You are strongly encouraged to find a topic on your own.

Here are some places where you can look for topics. A good source is the Electronic Colloquium on Computational Complexity where you can find much exciting recent work in the subject. You can also browse recent proceedings of FOCS, STOC, or CCC (the Conference on Computational Complexity), though many papers from there appear (in more readable form) on ECCC. Some of the readings may require too much background reading so feel free to talk to me if you are not sure the project is appropriate. ECCC has several excellent surveys on various topics that you can do (and explore further if you feel motivated).

The suggestions below vary somewhat in terms of "difficulty" and preparation
time. I am providing a subjective rating from * (easier) to *** (harder).
You should *not* choose your project based on the difficulty level;
choose a topic that you like or you are interested in. These indicators are
merely there to help you plan your time more effectively near the end of the
semester.

In one of the first lectures we saw that P ≠ EXP and NP ≠ NEXP. These are
examples of *time hierarchy theorems*, as they say that given more time we
can do more things. What if we allow the algorithms to use randomness? Surprisingly
the answer is not known. A good starting point for this project is the survey

- Lance Fortnow and Rahul Santhanam: A survey of time hierarchies

In our treatment of NP we measure hardness with respect to the size of the
instance and not the size of the witness. But is the real hardness determined by the
instance size or the witness size? One way to formalize and answer this question is
via *compressibility*:

- Danny Harnik and Moni Naor: On the Compressibility of NP Instances and Cryptographic Applications
- Lance Fortnow and Rahul Santhanam: Infeasibility of Instance Compression and Succinct PCPs for NP

Circuit and formula lower bounds are very hard to prove, yet recently there has been some progress in the arithmetic setting:

- Ran Raz: Multilinear Formulas for Permanent and Determinant are of Super-Polynomial Size
- Ran Raz: Multilinear
NC
_{1}≠ multilinear NC_{2} - Ran Raz, Amir Shpilka, and Amir Yehudayoff: A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

The Nisan-Wigderson paradigm assumes *circuit* lower bounds to achieve derandomization.
Can we obtain the same results using *uniform* lower bounds, e.g., EXP ⊄ BPP?

- Luca Trevisan and Salil Vadhan: Pseudorandomness and Average-Case Complexity via Uniform Reductions
- Russell Impagliazzo and Avi Wigderson: Randomness vs. Time: De-randomization under a uniform assumption

Applications to the Nisan-Wigderson generator extend beyond giving evidence for BPP = P. They can be used to eliminate randomness from interactive proofs, approximate sampling algorithms, and so on. Some of these applications are described in

- Ronen Shaltiel and Chris Umans: Pseudorandomness for Approximate Counting and Sampling
- Ronen Shaltiel and Chris Umans: Simple Extractors for All Min-Entropies and a New Pseudorandom Generator
- Peter Bro Miltersen and N. V. Vinodchandran: Derandomizing Arthur-Merlin games using hitting sets
- Dieter van Melkebeek and Adam Klivans: Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses

The PCP theorem used to be proved along the same lines as the NEXP ⊂ PCP proof from class, but with much more intricate constructions. Recently Irit Dinur came up with a completely different proof of the PCP theorem. However reading her proof requires some background in expander graphs and a few other things we did not cover in class.

- Irit Dinur: The PCP theorem by gap amplification