# 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

- ETH, lower bounds for Dominating Set and q-Dominating Set.
- Further Reading: [Impagliazzo, Paturi '01], [Impagliazzo, Paturi, Zane '01], [Patrascu, Williams '10]

Lecture 03

- SETH, SETH-based lower bound for q-Dominating Set, OVH, OVH-based lower bound for Longest Common Subsequence
- Further Reading: CT-PTP Slide 2, [Impagliazzo, Paturi '01], [Bringmann,Künnemann'15], [Abboud,Backurs,Vassilevska-Williams'15]

Lecture 04 + 05

- Polynomial Method for OV
- Further Reading: [Abboud, Williams, Yu '15], CPTP-Slide 3

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