Seminar Theoretische Informatik (WS 2022/23)
Organisatorisches
- Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7103, Tel. 0271-740-2826)
- Einführungstermin: Montag 11.Oktober, 14:00-16:00, H-C 7326
- Die Vorträge werden am 7. Februar 2023 im Raum H-A 7103 stattfinden.
Themen
In dem Seminar werden ausgewählte Themen aus der theoretischen Informatik behandelt. Wir beabsichten zu jedem der folgenden Themenkomplexe Vorträge anzubieten.
- Decision tree complexity (3 Vorträge)
- Solution of the sensitivity conjecture (1 Vortrag)
- Quanten-Suchalgorithmen (1 Vortrag)
- Streaming-Algorithmen und Kommunikationskomplexität (3 Vorträge)
- Streaming-Algorithmen für Dyck-Sprachen (1 Vortrag)
Programm
| Datum | Thema | Vortragender | Betreuer | |
| 1. | 7.2.2023, 8:30-10:00 | Decision Tree Complexity | Markus Lohrey | |
| 2. | 7.2.2023, 10:00-11:30 | Solution of the Sensitivity Conjecture | Andreas Lizenberger | Markus Lohrey |
| 3. | 7.2.2023, 12:30-14:00 | Quanten-Suchalgorithmen | Jesse Schäfer | Markus Lohrey |
| 4. | 7.2.2023, 14:00-15:30 | Streaming-Algorithmen für Dyck-Sprachen | Alexander Kampen | Markus Lohrey |
Literatur
- Harry Buhrman and Ronald de Wolf, Complexity measures and decision tree complexity: a survey (Thema 1)
- Rohan Karthikeyan, Siddharth Sinha, Vallabh Patil, On the resolution of the sensitivity conjecture (Thema 1 und 2)
- Uwe Schöning, Gems of Theoretical Computer Science (Thema 3)
- Tim Roughgarden Communication Complexity (Thema 4)
- Frédéric Magniez, Claire Mathieu, and Ashwin Nayak, Recognizing Well-Parenthesized Expressions in the Streaming Model (Thema 5)