Lehrende/r: Dr. rer. nat. Markus Blumenstock
Veranstaltungsart: Vorlesung/Übung
Anzeige im Stundenplan: 08.079.23011
Semesterwochenstunden: 4
Credits: 6,0
Unterrichtssprache: Deutsch
Min. | Max. Teilnehmerzahl: - | -
Voraussetzungen / Organisatorisches: Kenntnisse in Komplexitätstheorie und Mathematik (ausgenommen Statistik) werden vorausgesetzt. DSEA und FSB schaden sicher nicht, sind aber nicht notwendig. Die Vorlesung findet als Tafelvortrag statt. Das Skript wird getext und in Overleaf verfügbar gemacht.
Inhalt: - Zeithierarchiesatz ("mehr Zeit löst mehr Probleme" und P != EXPTIME) - Ladner's Theorem ("NP-Intermediate Problems") - Zero-Knowledge Proofs - Polynomialzeithierarchie - Schaltkreiskomplexität - Randomisierte Komplexität - (Schwaches) PCP Theorem und Approximationsschwere Geplant sind, soweit die Zeit reicht, weitere Themen: - Complexity within P - Expander-Graphen - Derandomisierung - Zählkomplexität - PAC-Learning und Boosting
Empfohlene Literatur: S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
Digitale Lehre: Eingesetzte Plattformen: LMS, Overleaf.
