Seminar Theoretical Computer Science (WS 2025/26)

 

Organization

• Organizer: Prof. Dr. Markus Lohrey (room H-A 7103, phone 0271-740-2826)
• Introduction meeting: October 13, 14:15-15:45, H-C 7326
• Presentations will be scheduled for late January or early February 2026.

---

 

Topics

In the seminar, selected topics from theoretical computer science will be covered. We intend to offer presentations on each of the following subject areas.

1. New Proof of the Schwartz-Zippel Lemma (1 talk)
2. Tree canonization using polynomials (1 talk)
3. Balancing straight-line programs (2 talks)
4. Testing equalities of straight-line programs a la Jez (2 talks)
5. The reachability theorem for finite groups (1 talk)
6. Probabilistic algorithms and complexity classes (up to 2 talks)
7. Communication complexity and streaming algorithms (up to 4 talks)
8. Tree evaluation is in space O(log n · log log n) (2 talks)
9. Simulating time in square-root space (2 talks)
10. Grover's quantum search algorithms (up to 2 talks)

 

Further literature for topic 4

• Complexity and Randomness in Group Theory GAGTA BOOK 1, Section 4.6.2 and 4.6.3

Further literature for topic 5

• Complexity and Randomness in Group Theory GAGTA BOOK 1, Section 4.6.8.2

Literature for topic 6

• Uwe Schöning, Gems of Theoretical Computer Science, Chapter 17 (available from the seminar organizer)

Literature for topic 10

• Uwe Schöning, Gems of Theoretical Computer Science, Chapter 26 (available from the seminar organizer)
• Love Grover, A fast quantum mechanical algorithm for database search
• Love Grover, From Schrödinger’s Equation to the Quantum Search Algorithm
• Richard Lipton, Kenneth Regan, Introduction to Quantum Algorithms via Linear Algebra, Chapter 13 (available from the seminar organizer)