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

• Übung 1
• Übung 2
• Übung 3
• Übung 4

 

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