..
Suche
Hinweise zum Einsatz der Google Suche
Personensuchezur unisono Personensuche
Veranstaltungssuchezur unisono Veranstaltungssuche
Katalog plus

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