Picture of Dmitry Itsykson Dmitry Itsykson

I am a leading researcher at Laboratory of Mathematical Logic of
Steklov Institute of Mathematics at St.Petersburg.

Research papers

  • Dmitry Itsykson, Artur Riazanov
    Proof complexity of natural formulas via communication arguments.
    ECCC Report TR20-184. To appear in proceedings of CCC 2020.

  • Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov
    Lower Bounds on OBDD Proofs with Several Orders.
    ECCC Report TR20-73. To appear in ACM Transactions on Computational Logic.

  • Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
    Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
    ECCC Report TR19-178. To appear in Computational Complexity.

  • Dmitry Itsykson and Dmitry Sokolov
    Resolution over linear equations modulo two.
    Annals of Pure and Applied Logic, Volume 171, Issue 1, January 2020. doi

  • Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
    Bounded-depth Frege complexity of Tseitin formulas for all graphs
    ECCC Report TR19-020. In proceedings of MFCS-2019.

  • Ludmila Glinskih and Dmitry Itsykson
    On Tseitin formulas, read-once branching programs and treewidth
    ECCC Report TR19-020. Draft [pdf]. In proceedings of CSR 2019. Full version appeared in Theory Comput. Syst. 65(3): 613-633 (2021)

  • Sam Buss, Dmitry Itsykson, Alexander Knop and Dmitry Sokolov
    Reordering Rule Makes OBDD Proof Systems Stronger
    ECCC Report TR18-041. In proceedings of CCC 2018.

  • Dmitry Itsykson and Alexander Knop
    Hard satisfiable formulas for splittings by linear combinations
    In Proceedings of SAT 2017 [pdf].

  • Ludmila Glinskih and Dmitry Itsykson
    Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
    In Proceedings of MFCS 2017: 26:1-26:12 [pdf].

  • Dmitry Itsykson, Alexander Knop, Andrei Romashchenko and Dmitry Sokolov
    On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables.
    Extended abstract was published in proceedings of STACS 2017: 43:1-43:14 [pdf]. Full version is available as ECCC Report TR19-001

  • Dmitry Itsykson, Alexander Okhotin and Vsevolod Oparin
    Computational and proof complexity of partial string avoidability
    In Proceedings of MFCS 2016. Full version in ACM Trans. Comput. Theory 13(1): 6:1-6:25 (2021) [pdf].

  • Dmitry Itsykson, Vsevolod Oparin, Mikhail Slabodkin and Dmitry Sokolov
    Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles
    Fundamenta Informaticae vol. 145, no. 3, pp. 229-242, 2016.

  • Dmitry Itsykson, Alexander Knop and Dmitry Sokolov
    Complexity of distributions and average-case hardness
    ECCC Report TR15-174. Accepted to ISAAC 2016.

  • Dmitry Itsykson, Alexander Knop and Dmitry Sokolov
    Heuristic time hierarchies via hierarchies for sampling distributions
    ECCC Report TR14-178 Accepted to ISAAC 2015.

  • Dmitry Itsykson, Mikhail Slabodkin and Dmitry Sokolov
    Resolution complexity of perfect matching principles for sparse graphs
    ECCC Report TR14-093. Accepted to CSR 2015. Draft [.pdf].

  • Dmitry Itsykson and Dmitry Sokolov
    Lower bounds for splittings by linear combinations.
    Accepted to MFCS-2014. Draft (updated 09.08.2014).

  • Dmitry Itsykson and Dmitry Sokolov
    On fast non-deterministic algorithms and short heuristic proofs.
    Fundamenta Informaticae, 132(1):113-129, 2014. Draft [.pdf].

  • Dmitry Itsykson and Vsevolod Oparin
    Graph expansion, Tseitin formulas and resolution proofs for CSP.
    In proceedings of CSR 2013, LNCS 7913: 162-173. Draft [.pdf].

  • Edward A. Hirsch and Dmitry Itsykson,
    On an optimal randomized acceptor for graph nonisomorphism.
    Information Processing Letters, 112: 166-171, 2012. Draft [.pdf].

  • Dmitry Itsykson and Dmitry Sokolov
    Lower bounds for myopic DPLL algorithms with a cut heuristic.
    In proceedings of ISAAC 2011. ECCC Report TR12-141. [pdf]

  • Edward A. Hirsch , Dmitry Itsykson, Valeria Nikolaenko and Alexander Smal
    Optimal heuristic algorithms for the image of an injective function
    ECCC Report TR11-091. Zapiski Nauchnyh Seminarov POMI (Journal of Mathematical Sciences), 399:15-32, 2012.

  • Edward A. Hirsch , Dmitry Itsykson, Ivan Monakhov and Alexander Smal
    On optimal heuristic randomized semidecision procedures, with application to proof complexity and cryptography.
    ECCC Report TR10-193. [pdf]. Theory of Computing Systems 51:179-195, 2012.

  • Dmitry Itsykson and Dmitry Sokolov
    The complexity of inversion of explicit Goldreich's function by DPLL algorithms
    Zapiski Nauchnyh Seminarov POMI (Journal of Mathematical Sciences), 399:88-109, 2012 [pdf]. Preliminary version appeared in proceedings of CSR 2011, LNCS 6651 pp. 134-147.

  • Edward A. Hirsch and Dmitry Itsykson,
    On optimal heuristic randomized semidecision procedures, with application to proof complexity.
    ArXiv preprint arXiv:0908.2707v2 [cs.CC], in proceedings of STACS 2010, pp.453-464.

  • Dmitry M. Itsykson,
    Lower bound on average-case complexity of inversion of Goldreich function by "drunken" backtracking algorithms.
    PDMI PREPRINT 3/2009. [ps.gz] (in Russian). In proceedings of CSR 2010, LNCS 6072, pp. 204-215. The paper won Yandex best paper award. Draft [.pdf]. To appear in Theory of Computing Systems.

  • Dmitry M. Itsykson,
    Structural complexity of AvgBPP.
    ECCC Report TR08-073, [ps], [pdf]. Annals of Pure and Applied Logic, 162(3): 213-223, 2010. Preliminary version appeared in proceedings of CSR 2009, LNCS 5675, pp. 155-166, 2009. The paper won Yandex best student paper award.

  • Edward A. Hirsch and Dmitry M. Itsykson,
    An infinitely-often one-way function based on an average-case assumption.
    ECCC Report TR07-117. [ps] , [pdf] Algebra and Analisys, 21(3):129--143, 2009. English translation: St. Petersburg Mathematical Journal, 21(3): 459-468, 2010. Preliminary version appeared in proceedings of WoLLIC 2008, LNCS 5110, pp. 208-217.

  • Dmitry Itsykson and Arist Kojevnikov,
    Lower bounds of static Lovasz-Schrijver calculus proofs for Tseitin tautologies
    Zapiski Nauchnyh Seminarov POMI, 340:10-32, 2006 (in Russian), [ps.gz]. English translation appeared in Journal of Mathematical Sciences 145(3):4942-4952, 2007, [pdf].
    Preliminary version appeared as Exponential Lower Bound on the Size of Static Lovasz-Schrijver Calculus in Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), pp. 323-334, [doi].

  • M. Alekhnovich, E. A. Hirsch, D. Itsykson,
    Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas.
    Extended abstract appears in Proceedings of ICALP 2004, LNCS 3142, 2004, pp.84-96. Full article appeared in Journal of Automated Reasoning (2005) 35: 51-72, [ps], [pdf].