Complexity Theory Markus Bläser



The exams will be oral, either online via Zoom or in person on campus (depending on your preferences and the pandemic situation). It will take about 45 minutes. The exams can be essentially anytime between end of July and mid of October, with a few exceptions. However, we would like to group the exams whenever possible for efficiency reasons. If you want to schedule an exam, send an email to Markus Bläser with your preferred date(s) and mode (online/in person). Below we will maintain a list of already scheduled exam dates. When possible, try to pick a date from there

  • September 6 (Benenson)
  • September 10 (Stieling)
  • September 20 (Geier, Lauer, Esmer)
  • September 27 (Mansion)
  • October 13 (Pham)


What to expect?

A typical starting question might be "How does a randomized Turing machine work and how are the corresponding classes defined?¨ A good answer to this question is longer than two sentences. Such questions give you the chance to talk about some topic and should seize this opportunity. More specific questions might be "What does the Valiant-Vazirani theorem state?" and "What are the main proof ideas?" . Of course we do not expect a full proof, but a good answer should provide the main ideas and concepts.


What not to expect?

You will not be asked to solve certain exercises.




Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators