COT 6421 Presentations
Your final assignment in COT 6421 is to prepare an oral presentation
to be presented to the class at the end of the semester.
The presentation can be an any topic in theoretical computer science.
It is to be presented in the style of a conference talk, which means
that you will need to prepare slides using PowerPoint or Latex.
As in a conference talk, you will be tightly limited in time, which
means that you will need to prepare and practice carefully so that
you can communicate the important ideas in a short amount of time.
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
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:
Over the next few weeks, think about whether you want to present individually
or in a group, and think about what topic you would like to present.
Then meet with me to get my approval.
Please do this by the end of March.
I expect that we will schedule the talks during the last two weeks
of classes---the weeks of April 11 and April 18.
- 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.