Fine-grained algorithms and complexity

This course will next be offered in the summer term 2021 (Link to official course page).

This course was offered in the summer term 2020 (Link to official course page).

Description

For the past almost 60 years, optimization problems were considered to be computationally tractable if they can be solved in polynomial time. This paradigm originates from the Cobham-Edmonds thesis of 1965. However, we are now in the age of big data, were often optimization problems must be solved on data sets for which polynomial-time with super-linear run time are too slow. The recent theory of "fine-grained complexity and algorithms provides a detailed view into the exact run times of polynomial time algorithms. The main achievement of this theory are fine-grained reductions between fundamental polynomial-time solvable problems. Two main achievements are obtained by this: First, faster polynomial-time algorithms are discovered for some problems, often improving decade-old run time bounds. Second, for some problems, strong evidence is given why researchers have struggled for so long to improve cubic-time or quadratic-time algorithms to linear-time algorithms: namely, the theory allows one to show that subcubic-time or subquadratic-time algorithms are highly unlikely to exist.

In this seminar we will discuss fascinating algorithms and complexity theory of this modern field of algorithm design.

Tasks

The seminar will cover 14 topics related to fine-grained algorithms and complexity. Each topic will be covered by one student, who will present the topic in a 25-minute presentation and a written report of 5-10 pages.

Requirements

Basic understanding of algorithms and their analysis. Concepts of polynomial-time, NP-completeness, and problem reductions. Knowledge of LaTeX for typesetting the report.

Setup

Max. of 14 participants, 4 appointments à 90 mins. Amount of ECTS depends on your degree program.