Letztes Semester

Komplexitätstheorie II

Dozent:innen: Dr. rer. nat. Markus Blumenstock
Kurzname: 08.079.23011
Kurs-Nr.: 08.079.23011
Kurstyp: Vorlesung/Übung

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.

Digitale Lehre

Eingesetzte Plattformen: LMS, Overleaf.

Empfohlene Literatur

S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

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

Termine

Datum (Wochentag)	Zeit	Ort
17.04.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik
24.04.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik
08.05.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik
15.05.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik
22.05.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik
05.06.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik
12.06.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik
19.06.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik
26.06.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik
03.07.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik
10.07.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik
17.07.2023 (Montag)	10:15 - 11:45	04 426 2413 - Neubau Physik/Mathematik