For your final project, you can do one of two things.

- Choose a chapter in the Arora-Barak book that we did not cover in class and study it. Keep track of all the issues you find unclear to be used as feedback for the final version of the book.
- Read a complexity theory related paper of your choice. There is a list of suggestions below.

If you choose to read a paper, here are some suggestions of topics, though you can feel free to choose your own. A good source is the Electronic Colloquium on Computational Complexity where you can find much exciting recent work in the subject. 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. There are several excellent surveys on various topics that you can do (and explore further if you feel motivated).

- NP complete problems and physical reality by Scott Aaronson
- P, NP, and mathematics - a computational complexity perspective by Avi Wigderson, on the role of complexity theory in mathematics

- A personal view of average-case complexity by Russell Impagliazzo. This short survey remains very influential in complexity even 12 years after its publication.
- On promise problems by Oded Goldreich
- A survey of time hierarchies by Lance Fortnow and Rahul Santhanam. The state of the art on time hierarchy theorems, including interesting recent work on hierarchy theorems for randomized computation.

- If NP languages are hard in the worst case then it is easy to find their hard instances by Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma
- On approximate majority and probabilistic time by Emanuele Viola explains the proof of the Sipser-Lautemann theorem and its relation to circuit lower bounds.
- Derandomized squaring of graphs by Eyal Rozenman and Salil Vadhan proves
Reingold's theorem that
*USTCON*is in logspace. - Parallel repetition: a simplified proof by Thomas Holenstein. This a very difficult paper, but if you feel inspired have a shot at it.

The project presentations will take place during class time on Thu Apr 26.

3.20 - 4.20 | Lihong: Attacks on P versus NP Ana Paula: NP complete problems in mathematics Saman: NP complete problems and quantum computation |

4.30 - 5.30 | Dev: The parallel repetition theorem Fengming: BPP in Σ _{2} and circuit lower boundsBegumhan: Decision tree complexity |