## Fine-grained algorithms and complexity

*This course is taught in English. This course will next be offered in the summer term 2021.*

*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.