Lecture Highlights of Theoretical Computer Science (Summer 2025)
| Type: | Lecture with Exercises |
|---|---|
| Programs: | BSc & MSc CS, ITS, AI, Mathematics |
| Lecturers: | Michael Walter, Thomas Zeume |
| Teaching Assistant: | Marko Schmellenkamp |
| Time and Place: |
Lectures: Tue 10-12 and Thu 10-12 (MC 1.54) Exercises: TBD |
| First meeting: | TBD |
| Credits: | 9-10 CP |
| Contact time: | 4+2 SWS |
| Language: | English |
| Course number: | 211057 |
| Links: | Moodle, VVZ |
Course Description & Syllabus
TLDR: 🙌 If you enjoyed your first course in theoretical computer science in the Bachelor’s and would like to deepen your knowledge by getting an overview of the fascinating theory of computing, then this course will be exactly right for you! 🙌
The insights of modern theoretical computer science are key for advances in all areas of computer science. In this course, we will discuss some highlights and the techniques that underpin them.
Possible topics that we might cover:
- Computational models (is there life beyond Turing machines?)
- Kolmogorov complexity (what is the shortest program that produces some output?)
- Communication complexity (how many bits must Alice and Bob exchange to jointly solve a problem?)
- Fine-grained complexity (are some easy problems easier than others? and why?)
- Fast multiplication of numbers and matrices (can you beat the high-school method?)
- Randomness (does it really help to compute faster?)
- Circuit lower bounds (why is it so hard to prove that problems are hard?)
- Convex optimization (how to maximize profit if all you can ask are yes/no questions)
- Hardness of approximation (how easy is it to find near-optimal solutions?)
- Cryptography and computation (from assumptions to zero knowledge)
Prerequisites
Successful completion of an introductory course on theoretical computer science (covering formal languages, basics of complexity theory including NP-completeness and reductions, basics of computability theory). Interest and motivation to learn about theoretical concepts.
Literature
We will offer slides and handwritten lecture notes. There is no single textbook for the course. Two good starting points are:
- Arora, Barak. Computational Complexity: A Modern Approach. Cambridge University Press.
- Kozen. Theory of Computation. Springer. 2006.
We will give further pointers to the literature where needed.
Learning Outcomes
You will know some of the most important results and insights of modern theoretical computer science. You will learn approaches and techniques that go well beyond a first course. You will be able to recognize when these can be used and how to adapt them to new situations. You will be able to independently acquire new knowledge in this area.
← Back