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.

Description

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 downa 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.).

Topics + Further Reading

Lecture 01

  • Overview (conditional lower bounds, central problems), machine model, NFA acceptance lower bound.
  • Further Reading:  CT-PTP Slide 1

Lecture 02

    Lecture 03

    Lecture 04 + 05

     

    Tentative Schedule

    Lecture Tutorial Teacher Topic Exercises Due
    17 Oct MK Introduction  
    19 Oct MK Exponential Time Hypothesis  
    24 Oct KB SETH and OV-hardness for LCS  
    26 Oct Presence exercises (Exercise Sheet 0)
    31 Oct Holiday  
    02 Nov MK Polynomial Method  
    07 Nov MK Polynomial Method II Exercise Sheet 1
    09 Nov  
    14 Nov KB 3SUM  
    16 Nov KB 3SUM II  
    21 Nov Exercise Sheet 2
    23 Nov  
    28 Nov  
    30 Nov  
    05 Dec  
    07 Dec  
    12 Dec  
    14 Dec  
    19 Dec  
    21 Dec  
    02 Jan  
    04 Jan  
    09 Jan  
    11 Jan  
    16 Jan  
    18 Jan  
    23 Jan  
    25 Jan  
    30 Jan  
    01 Feb