For your final project, you can do one of two things.
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).
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