Labor für
Algorithmen und Komplexitätstheorie

Was macht ein Rechenproblem schwierig? Das ist die zentrale Frage in unserem Labor. Wir entwerfen effiziente Algorithmen für Rechenprobleme und beweisen untere Schranken für deren Komplexität in verschiedenen Rechenmodellen und unter verschiedenen Annahmen.

Zu den Forschungsgebieten gehören exakte und approximative Algorithmen für NP-schwere Probleme, feinkörnige Komplexität und Schaltkreiskomplexität.

Ausgewählte Veröffentlichungen

Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov

Polynomial formulations as a barrier for reduction-based hardness proofs

SODA 2023: 3245-3281

Ivan Mihajlin, Anastasia Sofronova

A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates

CCC 2022: 13:1-13:15

Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams

Circuit Depth Reductions

ITCS 2021: 24:1-24:20

Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, Maksim Nikolaev

Collapsing Superstring Conjecture

APPROX-RANDOM 2019: 26:1-26:23

Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala

Tight Lower Bounds on Graph Embedding Problems

J. ACM 64(3): 18:1-18:22 (2017)

Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov

A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function

FOCS 2016: 89-98

Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin

Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT

Algorithms 12(3): 35:1-35:17 (2016)

Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider

Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility

ITCS 2016: 261-270

Gruppenmitglieder

Alexander Kulikov, Leiter Forschungslabor
Hauptseite
Ivan Mihajlin, Forscher
Hauptseite