Skip to main content
Home

St. Petersburg Department
of Steklov Mathematical Institute
of Russian Academy of Sciences

27 Fontanka, St. Petersburg, Russia

Main menu

  • Institute structure
    • Administration
    • EIMI
    • Laboratories
    • Researchers
    • Academic council
    • Center of Research and Education
    • Publishing Department
    • Contacts
  • Activities
    • Conferences
    • Seminars
    • Dissertation Councils
    • Journal "Algebra and Analysis"
    • Journal "Zapiski Nauchnykh Seminarov POMI"
    • Preprints (partially in Russian)
    • Publications
  • Search
  • Resources
    • Video records
    • History of the Institute
    • Digital libraries (in Russian)
    • Links (in Russian)
    • Former Employees
    • Remembering Olga Ladyzhenskaya
    • PDMI Library

сложность в среднем

Дмитрий Михайлович Ицыксон

лаборатория математической логики и дискретной математики
Position: 
Leading Researcher
Scientific Degree: 
Doctor of Sciences
Email: 
dmitrits [at] pdmi.ras.ru
Scientific Interests: 
теория сложности вычислений
теория сложности доказательств
сложность в среднем
нижние оценки
теория графов
экспандеры
математическая логика
алгоритмы

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

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

Логотип СПбРАН

  • Русский Русский
  • English English