Seminar Theoretische Informatik (WS 2021/22)
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 weiteren Termine finden am 7. und 8. Februar 2022 statt. Der Raum wird noch bekannt gegeben.
Themen
In dem Seminar werden ausgewählte Themen aus der theoretischen Informatik behandelt. Wir beabsichten zu jedem der folgenden Themenkomplexe Vorträge anzubieten.
- Sensitivity of Boolean Functions (4 Vorträge)
- Cuckoo Hashing (1 Vortrag)
- Min-Cut Algorithmus von Stoer und Wagner (1 Vortrag)
- Quanten-Suchalgorithmen (1 Vortrag)
- Streaming-Algorithmen und Kommunikationskomplexität (3 Vorträge)
Programm
Raum wird noch bekannt gegeben.
Datum | Thema | Vortragender | Betreuer | |
1. | 7.2.2022, 09:00-10:30 | Sensitivity of Boolean Functions I | Mohammad Ejazi | Markus
Lohrey
|
2. | 7.2.2022, 10:30-12:00 | Sensitivity of Boolean Functions II | Michael Heep | Markus
Lohrey
|
3. | 7.2.2022, 13:30-15:00 | Cuckoo Hashing | Thorben Meiswinkel | Andreas
Rosowski
|
4. | 7.2.2022, 15:00-16:30 | Min-Cut Algorithmus von Stoer und Wagner | Yasser Abdellioua | Andreas
Rosowski
|
5. | 8.2.2022, 9:00-10:30 | Quanten-Suchalgorithmen | Mehdi Razi | Markus
Lohrey
|
6. | 8.2.2022, 10:30-12:00 | Streaming-Algorithmen und Kommunikationskomplexität I | Andre Trapp | Markus
Lohrey
|
7. | 8.2.2022, 13:30-15:00 | Streaming-Algorithmen und Kommunikationskomplexität II | Arnaud Eric Toham Waffo | Markus
Lohrey
|
Literatur
- Rohan Karthikeyan, Siddharth Sinha, Vallabh Patil, On the resolution of the sensitivity conjecture (Thema 1)
- Rasmus Pagh, Cuckoo Hashing for Undergraduates (Thema 2)
- Mechthild Stoer, Frank Wagner, A Simple Min-Cut Algorithm (Thema 3)
- Uwe Schöning, Gems of Theoretical Computer Science (Thema 4)
- Tim Roughgarden Communication Complexity (Thema 5)