算法和复杂性
理论实验室

是什么使计算问题变得复杂？ 这是我们实验室的主要问题。 我们为计算问题设计了有效的算法，并在各种计算模型和各种假设下证明了其复杂性的下限。

研究领域包括 NP-hard 问题的精确和近似算法、细粒度的复杂性和电路复杂性。

精选出版物

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

小组成员

Alexander Kulikov, 研究实验室负责人
主页
Ivan Mihajlin, 研究员
主页