Final project information

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.

In either case, you are expected to write a short report (3-4 pages) and present it in class near the end of the semester. The presentations should be about 20 minutes long. You can choose to work either individually or in pairs.

Possible topics

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).

Essays on complexity

• 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

Technical surveys

• 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.

Some recent works

• 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.