Seminar Theoretische Informatik (WS 2024/25)
Organisatorisches
- Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7103, Tel. 0271-740-2826)
- Einführungstermin: Montag 14.Oktober, 14:15-15:45, H-C 7326
- All talks will take place on February 3, 2025, in room H-A 7101.
Topics
In dem Seminar werden ausgewählte Themen aus der theoretischen Informatik behandelt. Wir beabsichten zu jedem der folgenden Themenkomplexe Vorträge anzubieten.
- Quantum search algorithms (1 talk)
- The Morris counter (1 talk)
- Streaming algorithms and communication complexity (up to 3 talks)
- Streaming-Algorithms for Dyck-languages (1 talk)
Programm
| Datum | Thema | Vortragender | Betreuer | |
| 1. | 3.2.2025, 9:00-10:30 | Quantum search algorithms | Marcel Nils Pommert | Markus Lohrey
|
| 2. | 3.2.2025, 10:30-12:00 | Streaming algorithms and communication complexity | Ben Ehrengruber | Markus Lohrey
|
| 3. | 3.2.2024, 13:30-15:00 | The Morris counter | Marco Bender | Markus Lohrey
|
Literatur
- Uwe Schöning, Gems of Theoretical Computer Science, Chapter 26 (Topic 1)
- Love Grover, A fast quantum mechanical algorithm for database search (Topic 1)
- Love Grover, From Schrödinger’s Equation to the Quantum Search Algorithm (Topic 1)
- Richard Lipton, Kenneth Regan, Introduction to Quantum Algorithms via Linear Algebra, Chapter 13 (Topic 1)
- Robert Morris, Counting large numbers of events in small registers, Commun. ACM 21(10): 840-842 (1978) (Topic 2). A good exposition can be also found here .
- Tim Roughgarden, Communication Complexity (Topic 3)
- Frédéric Magniez, Claire Mathieu, and Ashwin Nayak, Recognizing Well-Parenthesized Expressions in the Streaming Model, Electron. Colloquium Comput. Complex. TR09 (2009) (Topic 4)
- Frédéric Magniez, Claire Mathieu, and Ashwin Nayak, Recognizing Well-Parenthesized Expressions in the Streaming Model, SIAM J. Comput. 43(6): 1880-1905 (2014) (Topic 4)