Fine-Grained Complexity

Modulnummer: Q06-18
Englischer Titel: Fine-Grained Complexity
Leistungspunkte: 6
Lehrperson: Kratsch

Empfohlene Vorkenntnisse

Solide Grundkenntnisse zu Algorithmen und Komplexität.

Zwingende Voraussetzungen

Es kann nicht auch Q10-31 Fine-Grained Analysis of Algorithms (4+2) eingebracht werden. Dieses Modul wird allerdings nicht mehr angeboten.

Inhalt

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.

Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung

- schriftlich eingereichte und/oder mündlich vorgetragene Lösungen zu Aufgaben

Lehrveranstaltungen

Vorlesung: 3 SWS
Übung: 1 SWS

Zugeordneter Vertiefungsschwerpunkt

Algorithmen und Modelle: ja
Modellbasierte Systementwicklung: nein
Daten- und Wissensmanagement: nein
Ohne Vertiefungsschwerpunkt: nein

Sprache im Modul

Deutsch: nein
Englisch: ja

Angeboten für Studiengänge

M. Sc.: ja
M. Ed.: ja
Wirtschaftsmaster: ja

Angeboten im

Wintersemester: ja
Sommersemester: ja

Turnus

Alle zwei Jahre