198:538 Complexity of Computation

Rutgers University, Computer Science Department, Spring 2007

Final project information

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

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

Technical surveys

Some recent works

Project presentation schedule

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 bounds
Begumhan: Decision tree complexity