This seminar is offered for students enrolled in the Mathematics Master as module S4C1 “Graduate Seminar on Discrete Optimization” as well as students enrolled in the Computer Science Master as module MA-INF 1205 with the same title. The seminar is organized and held by Prof. Dr. Anne Driemel.
The goal of the seminar is for each participant to:
If you want to participate in the seminar, please contact Prof. Dr. Anne Driemel with your topic preference from the literature list. The first preparation meeting will take place on Friday 29. January 2027 in room 2.074 (Informatik V, 2. OG) at 11 am. The meeting room is located in the computer science building at Friedrich Hirzebruch Allee 8.
Fine-grained complexity asks how fast computational problems can be solved, seeking to determine the precise running times of algorithms beyond the distinction between polynomial and exponential time. Hypotheses concerning problems such as SAT, 3SUM, all-pairs shortest paths, and hyperclique have guided this research by supporting conditional lower bounds for many other problems.
This graduate seminar explores recent breakthroughs that challenge these hypotheses and open new directions in algorithm design. Through selected foundational and recent papers, participants will study fine-grained reductions, algebraic techniques, and the consequences of faster algorithms for graph problems, computational geometry, and satisfiability. The seminar assumes familiarity with algorithms, complexity theory, and basic linear algebra.
The current state of the art is highly volatile. Some of the newer breakthrough results have been claimed, but have not been verified. This list will be frequently updated as things unfold.