Algoritmos e Complexidade
Laboratório Teórico

O que torna difícil um problema computacional? Esta é a pergunta que orienta nosso laboratório. Projetamos algoritmos eficientes para problemas computacionais e provamos os limites mínimos da sua complexidade em diferentes modelos computacionais e sob várias premissas.

As áreas de pesquisa incluem algoritmos exatos e aproximados para problemas NP-difíceis e complexidade de granularidade fina e de circuitos.

Publicações selecionadas

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

Membros do Grupo

Alexander Kulikov, Chefe de Laboratório
Página Inicial
Ivan Mihajlin, Pesquisador
Página Inicial