Lecture Complexity Theory II (Summer 2023)
Organisation
- Lecturer: Prof. Dr. Markus Lohrey (Room H-A 7103, Tel. 0271-740-2826)
- Lecture: Monday 8:00-10:00 in H-B 6414
- Tutorials: Monday 10:00-12:00 in H-B 6414 (Start: April 17, 2023)
- Tutorials take place in even weeks and are supervised by Michael Figelius.
Some topics
- Relativized complexity
- Monoton boolean circuits and Razborov's theorem
- Randomized complexity
- Interactive proof systems and Shamir's theorem
- Primes is in P
Slides
Exercises
Literature
- Sanjeev Arora und Boaz Barak: Complexity Theory: A Modern Approach. Cambridge University Press 2009
- Christo H. Papadimitriou: Computational complexity. Addison-Wesley 2005
- Ingo Wegener: Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. Springer 2003