The talks can be done individually, or you may do a group presentation with another student. For individual talks, you should plan on speaking for 20 minutes, followed by 5 minutes for questions. For group talks, plan on speaking for 30 minutes (15 minutes each).

You need to begin thinking about your presentation topic soon, and about whether you want to do an individual or group presentation. As I said above, you are free to choose any topic in theoretical computer science. But of course you need to choose something small enough to be presented effectively in a short amount of time. Especially good would be a presentation of some theoretical topic associated with your dissertation research. If you can't think of such a topic, here are some other possibilities:

- Marxen's work on the Busy Beaver Problem.
- Turing's 1936 paper.
- The proof that Primes is in P, due to Agrawal, Kayal and Saxena.
- The decidability of Presburger Arithmetic (Theorem 6.10 in Sipser).
- The Arithmetic Hierarchy.
- The Polynomial Hierarchy.
- Kolmogorov Complexity (Section 6.4 in Sipser).
- Immerman/Szelepcsenyi's proof that nondeterministic space is closed under complement (Theorem 8.22 in Sipser).
- Topics from Chapters 9 or 10 of Sipser.

Back to