News

Lecture tomorrow + exams

Written on 18.07.24 by Karl Bringmann

Dear students,

Please note that tomorrow, on Friday at 10:15, we have an irregular lecture. Also note that tomorrow the *room is 002 in E1 5*.

If you want to participate in the exam, please write an email to the lecturer in order to register, and also describe your availability on August 5. Also… Read more

Dear students,

Please note that tomorrow, on Friday at 10:15, we have an irregular lecture. Also note that tomorrow the *room is 002 in E1 5*.

If you want to participate in the exam, please write an email to the lecturer in order to register, and also describe your availability on August 5. Also don't forget to register in HISPOS.

New username for lecture recordings

Written on 21.06.24 by Karl Bringmann

Dear students,

For technical reasons the username for accessing the lecture recordings had to be changed. The password is still the same. You can find the updated information under Information -> Materials -> Recordings.

Lecture starts at 16:00

Written on 17.04.24 by Karl Bringmann

Dear students,

As decided in the lecture yesterday, from now on the lecture will always start at 16:00 sharp.

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). However, for practical purposes the label "polynomial-time" is too coarse: It can 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 relatively recently and the majority of the results taught in this course are less than ten years old.

Time & Date & Format

This course consists of one lecture per week (Tuesday 16:00-17:30) and a tutorial every other week (Friday 10:15-12:00).

The first lecture is on April 16. The first tutorial is held on April 26, then starting from May 03 a tutorial is held in every second week. Lectures and tutorials are held physically in room 024 building E1 4.

Prerequisites

We assume basic knowledge in algorithms and theoretical computer science, as taught in the basic 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" is useful, but 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 7 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 a written or oral exam.

Schedule

This is a tentative list of topics.

Lecture Tutorial Topic
Apr 16   Introduction
Apr 23   SAT Algorithms
  Apr 26 Q&A and presence exercises
Apr 30   Lower Bounds from P!=NP and ETH
  May 3 Tutorial
May 07   Lower Bounds from SETH and OVH: Hardness of LCS
May 14   Subcubic Equivalences of APSP 
  May 17 Tutorial
May 21   Subcubic Equivalences of APSP continued
May 24   Irregular Lecture Slot 10:15 - Matrix Multiplication and special cases of APSP
May 28   Lower bounds from 3SUM
  May 31 Tutorial
Jun 04   Cancelled
Jun 11   More lower bounds from 3SUM
  Jun 14 Tutorial
Jun 18   Zero Triangle: Counting and Cycle Removal
Jun 25   Cancelled
  Jun 28 Tutorial
Jul 02   Lower Bounds for Dynamic Problems
Jul 05   Irregular Lecture Slot 10:15 - Hardness of Approximation in P
Jul 09   Cancelled
  Jul 12 Tutorial
Jul 16   Subset Sum
Jul 19   Irregular Lecture Slot 10:15 - MinPlusConvolution, Knapsack
Jul 23   Lower Bounds from Sparser Problems + Outlook
  Jul 26 Tutorial

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. We closely follow the course from 2021.

Winter 2021: Fine-Grained Complexity Theory

Summer 2019: Fine-Grained Complexity Theory

Summer 2018: Selected Topics in Fine-Grained Complexity Theory

Winter 2017: Fine-Grained Complexity Theory

Summer 2016: Complexity Theory of Polynomial-Time Problems

Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.