Seminar Theoretische Informatik (WS 2023/24)
Organisatorisches
- Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7103, Tel. 0271-740-2826)
- Einführungstermin: Montag 9.Oktober, 14:15-15:45, H-C 7326
- All talks will be on January 31, 2024, 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.
- Decision tree complexity (up to 3 talks)
- Solution of the sensitivity conjecture (1 talk)
- Quantum search algorithms (1 talk)
- Streaming algorithms and communication complexity (up to 3 talks)
- Streaming-Algorithms for Dyck-languages (1 talk)
- Automaticity of languages (up to 2 talks)
Programm
| Datum | Thema | Vortragender | Betreuer | |
| 1. | 31.1.2024, 8:30-10:00 | Decision Tree Complexity I | Justus Krell | Rahul Jain |
| 2. | 31.1.2024, 10:00-11:30 | Decision Tree Complexity II | Pratik Sondkar | Rahul Jain |
| 3. | 31.1.2024, 14:30-16:00 | Automaticity of languages I | Lorena Stracke | Rahul Jain |
| 4. | 31.1.2024, 16:00-17:30 | Automaticity of languages II | Rebekka Jakob | Rahul Jain |
Literatur
- Harry Buhrman and Ronald de Wolf, Complexity measures and decision tree complexity: a survey (Topic 1)
- Rohan Karthikeyan, Siddharth Sinha, Vallabh Patil, On the resolution of the sensitivity conjecture (Topic 1 and 2)
- Hao Huang, Induced subgraphs of hypercubes and a proof of the sensitivity conjecture (Topic 2)
- Moses Charikar, Talk at the International Center for Theoretical Sciences, Bangalore (Topic 2)
- Love Grover, A fast quantum mechanical algorithm for database search (Topic 3)
- Love Grover, From Schrödinger’s Equation to the Quantum Search Algorithm (Topic 3)
- Richard Lipton, Kenneth Regan, Introduction to Quantum Algorithms via Linear Algebra, Chapter 13 (Topic 3)
- Uwe Schöning, Gems of Theoretical Computer Science, Chapter 26 (Topic 3)
- Tim Roughgarden, Communication Complexity (Thema 4)
- Frédéric Magniez, Claire Mathieu, and Ashwin Nayak, Recognizing Well-Parenthesized Expressions in the Streaming Model (Topic 5)
- Jeffrey Shallit, Yuri Breitbart, Automaticity I: Properties of a Measure of Descriptional Complexity (Topic 6)