2400152 – Fine-Grained Complexity Theory & Algorithms

This course introduces to the foundations of fundamental algorithmic barriers in the polynomial-time and exponential-time regimes. You will learn about fine-grained reductions to relate the time complexity of different problems and deriving conditional lower bounds from such reductions, based on established hardness assumptions. Furthermore, you will get to know techniques underlying the fastest known algorithms for central problems in the field. 

Allgemeine Informationen

Kursprogramm

Fine-grained reductions:
* Conditional lower bounds.
* Reduction techniques

Central hypotheses and their applications:
* (Strong) Exponential Time Hypothesis:
* Orthogonal Vectors Hypothesis.
* 3SUM Hypothesis
* APSP Hypothesis
* Lower Bounds for String Problems, Algorithmic Graph Theory, Geometry

Algorithmic techniques:
* fastest known algorithms for central problems (SAT, Orthogonal Vectors, 3SUM, APSP).
* Polynomial Method
* Applications of fast matrix multiplication
* Fast Fourier Transform/Polynomial Multiplication

Competencies / intended learning achievements:
Upon successful completion of the module, students will be able to:
* describe fundamental algorithmic barriers regarding exponential and polynomial runtime;
* relate algorithmic problems through fine-grained reductions to derive conditional lower bounds on run-time complexity;
* explain algorithmic techniques that lead to the fastest known algorithms for important algorithmic problems.

Veranstaltungsdaten

Dozent(en)

Prof. Dr. Marvin Künnemann

Studiengang

Informatik

Abschluß

Master

Start

17. Apr 2024

Ende

26. Apr 2024

Veranstaltungsart

Vorlesung/Übung

Ort

50.34 Room 301

Zyklus

wöchtl.

Zusammenfassung

This course introduces to the foundations of fundamental algorithmic barriers in the polynomial-time and exponential-time regimes.
You will learn about fine-grained reductions to relate the time complexity of different problems and deriving conditional lower bounds from such reductions, based on established hardness assumptions.
Furthermore, you will get to know techniques underlying the fastest known algorithms for central problems in the field. 

Allgemein

Sprache

Englisch

Schlagwörter

Fine-grained Complexity, Algorithm Design

Kontakt

Name

Mirza Redzic, Julian Stieß

E-Mail

mirza.redzic@kit.edu
julian.stiess@kit.edu

Verfügbarkeit

Zugriff

Unbegrenzt – wenn online geschaltet

Aufnahmeverfahren

Sie können diesem Kurs direkt beitreten.

Zeitraum für Beitritte

Unbegrenzt

Für Kursadministratoren freigegebene Daten

Daten des Persönlichen Profils

Anmeldename
Vorname
Nachname
E-Mail
Matrikelnummer

Zusätzliche Informationen

Objekt-ID

3120220