теория сложности

Заведующий:
ведущий научный сотрудник
Пономаренко Илья Николаевич
доктор ф.-м. наук
Сотрудники:
Страница лаборатории: 
http://logic.pdmi.ras.ru
Научные интересы: 
математическая логика
теория сложности
дискретная математика

Александр Сергеевич Куликов

лаборатория прикладных вероятностных и алгоритмических методов
Должность: 
ведущий научный сотрудник
Учёная степень: 
доктор ф.-м. наук
Email: 
alexander.s.kulikov [at] gmail.com
Телефон: 
+7 (812) 571-43-92
Местный телефон: 
1412
Домашняя страница: 
https://alexanderskulikov.github.io/
Научные интересы: 
алгоритмы
теория сложности

Образование:

2005, СПбГУ, мат-мех, специалитет

2009, ПОМИ РАН, к.ф.-м.н.

2017, ПОМИ РАН, д.ф.-м.н.

Публикации:

  1. 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

https://doi.org/10.1137/1.9781611977554.ch124

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

Circuit Depth Reductions. ITCS 2021: 24:1-24:20

https://doi.org/10.4230/LIPIcs.ITCS.2021.24

  1. 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)

https://doi.org/10.1145/3051094

  1. 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

https://doi.org/10.1109/FOCS.2016.19

  1. Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin:

Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. ACM Trans. Algorithms 12(3): 35:1-35:17 (2016) https://doi.org/10.1145/2847419

DBLP: https://dblp.org/pid/45/880.html

Scopus: https://www.scopus.com/authid/detail.uri?authorId=55211922700

Google.Scholar: https://scholar.google.com/citations?user=u3erCUkAAAAJ&hl=en