Fine-Grained Complexity Theory

Advanced Course, 3+1

Lectures: Tuesday + Thursday, 16:15 - 18:00, E1.4 024
Lecturers: Karl Bringmann and Marvin Künnemann
Tutorials: every second Thursday is an exercise session
Assistant: Philip Wellnitz
Credits: 6
Prerequisites: No formal requirements, but basic knowledge in algorithms & data structures and complexity theory is assumed.
Exam: The exam will be written and take place on Friday, August 9 at 9:30-12:30 in E1 3, room HS001. You may bring a handwritten one-sided cheat sheet. To be admitted to the exam, you need at least 50% of all points in the assignment sheets. If you are admitted to the exam, then you will also be admitted to the re-exam and can improve your grade. The re-exam will be written and take place on Thursday, September 5 at 13:30-16:30 in E1 3, room HS001.


  • On July 18th we start 20min late, i.e., the lecture is from 16:35-18:05
  • Room change on June 13th to the room 029 in MPI-SWS!
  • Room change on May 28th to the room 029 in MPI-SWS!
  • Room change on May 2nd to the room next door (E1.4 023)!
  • To register for the course, please subscribe to our mailing list under and send us an email with your name and matriculation number to {wellnitz,kbringma,marvin}


Complexity theory traditionally distinguishes whether a problem can be solved in polynomial time (by providing an efficient algorithm) or the problem is NP-hard (by providing a reduction). For practical purposes however the label "polynomial-time" is too coarse: it may make a huge difference whether an algorithm runs in say linear, quadratic, or cubic time. In this course we explore an emerging subfield at the intersection of complexity theory and algorithm design which aims at a more fine-grained view of the complexity of polynomial-time problems. We present a mix of upper and lower bounds for fundamental poynomial-time solvable problems, often by drawing interesting connections between seemingly unrelated problems. A prototypical result presented in this course is the following: If there is a substantially faster algorithm for computing all-pairs shortest paths in a weighted graph, then there also is a substantially faster algorithm for checking wether the graphs has a negative triangle (and vice versa). The techniques for proving such statements have been developed quite recently and most results taught in this course are less than five years old.

An important part of the course are the exercises, where you will design conditional lower bounds essentially on your own. There will be 6 exercise sheets and you need to collect at least 50% of all points on exercise sheets to be admitted to the exam. You are allowed to collaborate on the exercise sheets, but you have to write down a solution on your own, using your own words. Please indicate the names of your collaborators for each exercise you solve. Further, cite all external sources that you use (books, websites, research papers, etc.).


Lecture Tutorial Teacher Topic Exercises Due
9 April MK Introduction to Fine-Grained Complexity  
11 April MK Lower Bounds from P!=NP and ETH  
16 April MK Lower Bounds from SETH; LCS lower bound from OVH  
18 April Presence exercises  
23 April KB Primer to Randomness, Polynomial Method for OV  
25 April KB Polynomial Method for OV, continued  
30 April KB Polynomial Method for APSP Exercise Sheet 1
2 May Room change to 023!  
7 May KB APSP: Subcubic Equivalences  
9 May KB APSP: Subcubic Equivalences, continued  
14 May MK BMM and Combinatorial Algorithms Exercise Sheet 2
16 May  
21 May MK 3SUM: Algorithms I  
23 May MK 3SUM: Algorithms II and Lower Bounds I  
  28 May Room Change to 029 MPI-SWS! Exercise Sheet 3
30 May Canceled due to holiday  
4 June MK 3SUM: Lower Bounds II  
6 June MK Partial relations among SETH, 3SUM, APSP I  
11 June MK Partial relations among SETH, 3SUM, APSP II Exercise Sheet 4
13 June Room change to 029 MPI-SWS!  
18 June KB SETH-Hardness of Subset Sum  
20 June Canceled due to holiday  
25 June PW Efficient Computation with Polynomials Exercise Sheet 5
27 June  
2 July KB Nondeterministic SETH  
4 July KB Randomized Nondeterministic SETH is false  
9 July MK Multivariate Analysis  
11 July  
16 July KB Hardness of Approximation in P  
18 July KB (Min,+) Convolution