Lecture Highlights of Theoretical Computer Science (Summer 2024)
Type: 
Lecture with Exercises 
Programs: 
BSc & MSc CS, ITS, AI, Mathematics 
Lecturers: 
Vladimir Lysikov,
Michael Walter,
Thomas Zeume

Teaching Assistants: 
Marko Schmellenkamp,
...

Time and Place: 
Lectures: Tue 10:0012:00 and Thu 10:0012:00 (MC 1.54)
Exercises: TBD

First meeting: 
TBD 
Credits: 
910 CP 
Contact time: 
4+2 SWS 
Language: 
English 
Course number: 
211057 
Links: 
Moodle,
VVZ

Interested in this course? If you plan on participating, please kindly sign up on Moodle so that we know how many people to expect.
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?)
 Finegrained complexity (are some easy problems easier than others? and why?)
 Fast multiplication of numbers and matrices (can you beat the highschool 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 nearoptimal 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 NPcompleteness and reductions, basics of computability theory). Interest and motivation to learn about theoretical concepts.
Literature
There is no single textbook for the course. Two good starting points are:
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