News
Zoom LinkWritten on 24.10.21 (last change on 24.10.21) by Karl Bringmann Please register on this course website to get access to lecture notes, exercise sheets, and the Zoom link. After registration, the Zoom link can by found under "Information" -> "Virtual Guide". |
Fine-Grained Complexity Theory
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 algorithms and conditional lower bounds for fundamental 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 whether the graph 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 ten years old.
Time & Date & Format
This course consists of one lecture per week (Monday 16:15-18:00) and a tutorial every other week (Friday 14:15-16:00).
The first lecture is on October 25. The lecture will be in a hybrid format, so you can join physically in room 024 building E1 4 or virtually on Zoom (the link can be found under "Information"->"Virtual Guide" after registering and logging into this website). A recording will be made available. We will discuss in the first lecture in what format the lecture should continue (physical+video / physical+Zoom / virtual-only).
Prerequisites
We assume basic knowledge in algorithms and theoretical computer science, as taught in the introductory courses "Grundzüge von Algorithmen und Datenstrukturen"/"Fundamentals of Algorithms and Data Structures" and "Grundzüge der Theoretischen Informatik"/"Introduction to Theoretical Computer Science". The core lecture "Algorithms and Data Structures" could be useful, but is no formal prerequisite.
Registration
You need to register on this webpage to get access to exercise sheets and other course material.
Exercises
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.).
Exam
To be admitted to the exam, you need to achieve 50% of the points on the exercise sheets. There will be an oral exam on February 24.
Schedule
This is a tentative list of topics.
Lecture | Tutorial | Topic |
---|---|---|
Oct 25 | Introduction | |
Nov 01 | No lecture - holiday | |
Nov 05 | Presence Exercises | |
Nov 08 | Lower Bounds from P!=NP and ETH | |
Nov 15 | Lower Bounds from SETH and OVH | |
Nov 19 | ||
Nov 22 | Subcubic Equivalences of APSP | |
Nov 29 | Subcubic Equivalences of APSP continued | |
Dec 03 | ||
Dec 06 | Matrix Multiplication and special cases of APSP | |
Dec 13 | Lower bounds from 3SUM | |
Dec 17 | ||
Jan 03 | More lower bounds from 3SUM | |
Jan 10 | Subset Sum lower bound from SETH | |
Jan 14 | ||
Jan 17 | Subset Sum algorithms | |
Jan 24 | Hardness of Approximation in P | |
Jan 28 | ||
Jan 31 | Lower Bounds for Dynamic Problems | |
Feb 07 | Outlook (recap, further hypotheses, multivariate lower bounds) | |
Feb 11 |
Literature
We do not follow a particular book. You can find slides and partial lecture notes from previous iterations of this course on the following webpages (however, the content of the previous iterations somewhat differs; essentially this year's iteration is a subset of the previous ones).
Summer 2019: Fine-Grained Complexity Theory
Summer 2018: Selected Topics in Fine-Grained Complexity Theory