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.

News

  • The oral exam will take place in February or March. Please mark possible dates in the following doodle, till January 23 at the latest: https://doodle.com/poll/g7p3h55gncrxpnhq

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 (17 Oct)

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

Lecture 02 (19 Oct)

    Lecture 03 (24 Oct)

    Lecture 04 + 05 (02+07 Nov)

      Lecture 06 (14 Nov)

      Lecture 07 (16 Nov)

      Lecture 08 (21 Nov)

        ...

        Lecture 13 (14 Dec)

        • Partial relations among SETH, 3SUM, APSP: Reduction from k-Clique to OV, non-tight reduction from k-SUM to k-OV

        Lecture 14 (19 Dec)

        • Partial relations among SETH, 3SUM, APSP: finished non-tight reduction from k-SUM to k-OV, k-SUM algorithm via polynomial multiplication, k-sum-free sets
        • Further Reading: [Behrend'46]

        Lecture 15 (02 Jan)

        • Partial relations among SETH, 3SUM, APSP: Reduction from k-Clique to OV, non-tight reduction from k-SUM to k-OV

        Lecture 16 (04 Jan)

        • Nondeterministic SETH: introduced (co-)nondeterministic algorithms and verification algorithms, showed that 3-SUM is efficiently verifiable
        • Further Reading: [CGIMPS'15]

        Lecture 17 (09 Jan)

        Lecture 18 (16 Jan)

        • Randomized Nondeterministic SETH is false; arithmetic circuits and the Schwartz-Zippel lemma
        • Further Reading: [Williams'16]

        Lecture 19 (18 Jan)

        • Hardness of Approximation in P: Assuming SETH, MaxInnerProduct has no 1.99-approximation in strongly subquadratic time
        • Further Reading: [Abboud,Rubinstein,Williams'17]

         

        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 algorithms  
        16 Nov KB 3SUM Lower Bounds  
        21 Nov KB/MK Convolution-3SUM Exercise Sheet 2
        23 Nov  
        28 Nov MK Subcubic Equivalences  
        30 Nov MK Subcubic Equivalences II  
        05 Dec MK Subcubic Equivalences III + BMM Exercise Sheet 3
        07 Dec  
        12 Dec MK BMM II  
        14 Dec KB Partial relations among SETH, 3SUM, APSP  
        19 Dec KB Partial relations among SETH, 3SUM, APSP II Exercise Sheet 4
        21 Dec  
        02 Jan KB Partial relations among SETH, 3SUM, APSP III  
        04 Jan KB Nondeterministic SETH  
        09 Jan KB Efficient Computation with Polynomials Exercise Sheet 5
        11 Jan  
        16 Jan KB Randomized Nondeterministic SETH is false  
        18 Jan KB Hardness of Approximation in P  
        23 Jan MK (Min,+) Convolution Exercise Sheet 6
        25 Jan  
        30 Jan MK Hardness for Dynamic Problems  
        01 Feb MK Lecture Wrap-Up, Glimps into the Future