Student Presentations

In the last part of this course, you will give a presentation to the class on some topic in complexity theory. The objective is to let you leverage your background in complexity theory to learn a new topic, understand it well, and present it to the class. This material is likely to be hard, so planning and executing a clear presentation is a challenge and, hopefully, a valuable learning experience! These presentations will occur in the last two weeks of the semester: The weeks of December 1 and December 8.

You are encouraged to work in pairs. Each pair will pick a topic (some sample topics are listed below, but you are welcome to propose a different topic as long as it is clearly in the area of computational complexity theory) and give a 75 minute presentation on that topic. If you strongly prefer to present individually that is permitted but it is more work and offers fewer opportunities to learn from working with a partner.

You (and your partner) should have your topic approved no later than Wednesday, November 5. This simply involves telling me what you would like to present. Keep in mind that if someone else has already proposed that topic, I may ask you to take on a different topic - so talking to me early is advisable.

Once you have your project topic approved, you should start looking for resources to help you prepare your presentation. You should submit your list of resources to me by Monday, November 10. On that date, I will also publish the schedule for the presentations.

Finally, you will be asked to prepare one short problem related to your presenation and your peers will be asked to work on that problem. You will be responsible for "grading" that problem with me.

Some Sample Topics

• Every language in DTIME(o(n log n)) is necessarily regular
• Any k-tape TM running in O(f(n)) time can be simulated by a 2-tape TM running in O(f(n) log f(n)) time. (The Hennie-Stearns Theorem)
• Approximation-preserving reductions
• Randomized complexity classes
• Parallel complexity classes
• Interactive proofs and the class IP
• The complexity of counting and the class #P