Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Algorithm Engineering

Sommersemester 2018
Professor Stefan Kratsch

For many fundamental polynomial-time solvable problems like Longest Common Subsequence or All-Pairs Shortest Paths there has been no substantial improvement in worst-case running time for decades. The area of Fine-Grained Analysis of Algorithms seeks to explain this lack of improvement. By careful reductions between problems it has been showed that progress for very different problems is often tightly related. E.g. there is a truly subcubic algorithm for All-Pairs Shortest Paths if and only if a bunch of other problems, like Minimum Weight Triangle, have truly subcubic algorithms. Similarly, many problems can only have faster algorithms if there is a breakthrough for solving the Satisfiability problem.

The lecture covers lower bounds for many fundamental problems. We will discuss the required complexity assumptions, e.g., the hypothesis that there are no truly subquadratic algorithms for the Orthogonal Vectors problem. By means of appropriate reductions we then get the lower bounds or even asymptotic equivalence for some problems. Optionally, we will discuss implications for dynamic problems, where input changes over time, and for certain NP-hard problems.    

Lecture and exercise are given in English.

Lecture and exercise times

Exam

The lecture is completed by passing an oral exam at the end of the term. To be admitted you need to satisfactorily solve two homework assignments. The oral exam alone determines the grade.

Exercises

In the exercise meetings you will work in teams of 2 or 3 to discuss and solve problems related to the current lecture content. It is welcome to prepare at home but the main work is done during these meetings. Prof. Kratsch will be around to answer questions, give hints, and verify your solution attempts.

Books

There are as of yet no books published on this very active topic. That said, you will be able to find survey talks (i.e. slides) on the topic by using your favorite web search engine. Some relevant papers will be shared via moodle or other means.