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

2008 Университет ИТМО, факультет информационных технологий и программирования, прикладная математика и информатика.

Публикации:

1. Ivan Mihajlin, Alexander Smal: Toward Better Depth Lower Bounds: The XOR-KRW Conjecture. CCC 2021: 38:1-38:24.
2. Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander V. Smal: Half-Duplex Communication Complexity. ISAAC 2018: 10:1-10:12.
3. Alexander V. Smal, Navid Talebanfard: Prediction from partial information and hindsight, an alternative proof. Inf. Process. Lett. 136: 102-104 (2018).
4. Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki: Gate elimination: Circuit size lower bounds and #SAT upper bounds. Theor. Comput. Sci. 719: 46-63 (2018).
5. Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal: On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography. Theory Comput. Syst. 51(2): 179-195 (2012).

https://dblp.uni-trier.de/pid/74/8864.html

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

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

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

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

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

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

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

2001 - 2006 Санкт-Петербургский государственный университет, математико-механический факультет, математическое обеспечение и администрирование информационных систем.

2006 - 2009 аспирантура ПОМИ РАН, защитил кандидатскую диссертацию «Сложность в среднем случае вероятностных вычислений с ограниченной ошибкой» в диссертационном совете при СПбГУ.

2022 защитил докторскую диссертацию «Нижние оценки и вопросы оптимальности для систем доказательств» в диссертационном совете при ПОМИ РАН.

Опыт работы:

ПОМИ РАН
2009 — 2011 м.н.с.

2011 — 2016 с.н.с.

2016 — 2017 ученый секретарь

2017 — наст. вр. в.н.с.

Санкт-Петербургский Академический университет РАН

2008 — 2010 преподаватель

2010 — 2019 доцент

СПбГУ

2018 — 2022 доцент

Награды:

Премия за лучшую статью на конференции CSR 2010;

Премия конкурса «Молодая математика России», 2018;

Премия за лучшую статью на конференции CSR 2019 (совместно с Л. Глинских).

Публикации:

1. Dmitry Itsykson, Dmitry Sokolov, Resolution over linear equations modulo two. Ann. Pure Appl. Log. 171(1) (2020)
2. Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov, On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables. J. Symb. Log. 85(2): 632-670 (2020)
3. Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal, On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography. Theory Comput. Syst. 51(2): 179-195 (2012)
4. Dmitry Itsykson, Structural complexity of AvgBPP. Ann. Pure Appl. Log. 162(3): 213-223 (2010)
5. Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson, Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. J. Autom. Reason. 35(1-3): 51-72 (2005)

Список публикаций на DBLP https://dblp.org/pid/31/4688.html