Лаборатория алгоритмов
и теории сложности

Что делает вычислительную задачу сложной? Это главный вопрос в нашей лаборатории. Мы разрабатываем эффективные алгоритмы для вычислительных задач и доказываем нижние границы их сложности в различных вычислительных моделях и при различных предположениях.

Области исследований включают точные и приближенные алгоритмы для задач недетерминированной полиномиальной сложности, тонкие оценки на время работы алгоритмов и сложность схем.

Избранные публикации

Татьяна Белова, Александр Головнев, Александр Куликов, Иван Михайлин, Денил Шарипов

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

Состав

Александр Куликов, Руководитель лаборатории
Профиль
Ivan Mihajlin, Исследователь
Профиль