알고리즘 및 복잡도
이론 실험실

계산 문제를 어렵게 만드는 것은 무엇인가요? 이것이 우리 연구실에 방향을 안내하는 질문입니다. 우리는 계산 문제를 해결하는 효율적인 알고리즘을 설계하고 다양한 계산 모델과 다양한 가정 하에서 복잡도의 하한을 입증합니다.

연구 분야에는 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, 연구원
홈페이지