# Fine-Grained Complexity Theory

 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 on March 6!

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

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 09 (28 Nov)

• finished equivalence of Lecture 08: analysis of hash function
• definition of fine-grained reductions, subcubic equivalence of (min,+) product and APSP

Lecture 10 (30 Nov)

Lecture 11 (5 Dec)

Lecture 12 (12 Dec)

• BMM-based lower bound for Sliding Window Hamming Distance
• Minimum Node-weighted Triangle: BMM lower bound and faster algorithm using fast matrix multiplication
• Further Reading:  [Czumaj,Lingas'07], CPTP-Slide 8

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

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

Lecture 17 (09 Jan)

Lecture 18 (16 Jan)

• Randomized Nondeterministic SETH is false; arithmetic circuits and the Schwartz-Zippel lemma

Lecture 19 (18 Jan)

• Hardness of Approximation in P: Assuming SETH, MaxInnerProduct has no 1.99-approximation in strongly subquadratic time

Lecture 20 (23 Jan)

• (min,+)-convolution: relation to APSP and 3SUM, equivalence to (min,+)-violation

Lecture 21 (30 Jan)

• OV-based lower bound for dynamic #SSR, OMv conjecture, OMv-based lower bound for SSR

Lecture 22 (1 Feb)

• recap + open problems

# 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, Glimpse into the Future