Saint Petersburg, 199178, Russia, Line 14th (Vasilyevsky Island), 29
(812) 363-68-71, (812) 363-68-72
ru en
Dmitry M. Itsykson
Dmitry M. Itsykson
Associate Professor
Contacts:

29 Line 14th (Vasilyevsky Island), 199178 Saint Petersburg, Russia

dmitrits@pdmi.ras.ru

https://logic.pdmi.ras.ru/~dmitrits/

Reception hours:

By appointment


Education

12.2008 — Ph.D. (C.Sc.) in Mathematics and Physics («Mathematical Logic, Algebra and Number Theory »)
Institution: St. Petersburg State University
Thesis title: Average case complexity of randomized computations with bounded error
Advisors: E.A. Hirsch

06.2009 — B.Sc. in Mathematics and computer science
Institution: St. Petersburg State University


Опыт работы

2018 — until now SPb State University, Associate Professor

2009 – until now St. Petersburg Department of Steklov Mathematical nstitute of Russian Academy of Sciences, Lead Researcher

2008 – 2019 SPb Academic University SB RAS, Associate Professor


Scientific interests

My work addresses topics in computational complexity and proof complexity


Selected publications

  1. Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov. Reordering rule makes OBDD proof systems stronger (2018). In Proceedings of CCC 2018. LIPIcs. Leibniz Int. Proc. Inform., 102 16:1-16:24.
  2. Dmitry Itsykson and Dmitry Sokolov. Lower bounds for splittings by linear combinations (2014).. In Proceedings of MFCS-2014, LNCS 8635: 372-383.
  3. Edward A. Hirsch , Dmitry Itsykson, Ivan Monakhov and Alexander Smal. (2012) On optimal heuristic randomized semidecision procedures, with application to proof complexity and cryptography. . Theory of Computing Systems 51:179-195
  4. Dmitry M. Itsykson. Structural complexity of AvgBPP (2010). Annals of Pure and Applied Logic, 162(3): 213-223.
  5. M. Alekhnovich, E. A. Hirsch, D. Itsykson. Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas (2005). ). Journal of Automated Reasoning 35: 51-72.