Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Introduction to Fine-Grained Complexity

MSc Lecture — Summer 2020

Organization

Due to the COVID-19 pandemic, this course will be offered online. Thus, it is important that all participants enroll by April 22 via our Moodle page.

Description

The term fine-grained describes the new branch of complexity theory where computational lower bounds are based on hypothesis other than \(\text{P} \neq \text{NP}\). Originating from the objective to derive bounds for polynomial time solvable problems, surprisingly powerful conjectures about best running-times for some classical problems have emerged. For example, the assumption that the all-pairs-shortest path problem can not be solved in subcubic time (APSP conjecture) implies the same lower bound for several other problems. The probably most surprising result of this type shows that the APSP conjecture implies that there is no subcubic algorithm for the negative-triangle problem (decide if an edge-weighted graph contains a triangle with weights that sum up to a negative number).

In this course we will discuss four conjectures from fine-grained complexity: SETH, OV, 3SUM and APSP. We will learn the reduction techniques to show computational lower bounds based on such conjectures and give classifications for many fundamental poynomial-time solvable problems. Later in the lecture, we will also see where the conjectures and ideas of fine-grained complexity are useful from the perspective of approximation and parameterized algorithms.

The goals of this course are to provide an overview of the complexity landscape within P (as far as currently established), teach the reduction techniques for lower bounds under SETH, OV, 3SUM and APSP, and further give some insight into the current trends in fine-grained complexity.

Requirements

There are no formal requirements for this course, however a basic understanding of algorithm design and analysis is expected. Knowledge about (classical) complexity theory is beneficial but not required.

Structure of This Course

At the weekly appointment, lecture and tutorial sessions will alternate. The tutorial is intended for questions as well as exercises and additional literature we will work through together; in particular, there will be no written homework assignments.

Examination

The grade for this course is fully determined by an oral exam of approximately 30 minutes with a time-slot that can be picked individually either in the week 3.-7. August or 21.-25. September. 

Language During This Course

This course will be taught in English. In case that all participants are fine with this course being taught in German, it can be switched to German.

Dates and Location

Wednesdays, from 13:30 to 15:00 in H-2.58.

Lectures start in the second week of lectures, that is, the first lecture starts on April 22.