Picture of Dmitry Itsykson Dmitry Itsykson

I am a non-faculty researcher at the Computer Science Department of the Ben-Gurion University of the Negev.

I am currently on leave from the Laboratory of Mathematical Logic of Steklov Institute of Mathematics at St.Petersburg, where I hold a leading researcher position.

Main page

Research papers

Contacts

Research papers

  • Yaroslav Alekseev and Dmitry Itsykson
    Lifting to bounded-depth and regular resolutions over parities via games.
    Electronic Colloquium on Computational Complexity, technical report TR24-128, 2024.

  • Dmitry Itsykson, Sergei Ovcharov
    On Limits of Symbolic Approach to SAT Solving.
    In Proceedings of SAT 2024: 19:1-19:22 [doi]

  • Klim Efremenko, Michal Garlik, Dmitry Itsykson
    Lower Bounds for Regular Resolution over Parities.
    In Proceedings of STOC 2024: 640-651. ECCC Report TR23-187

  • Dmitry Itsykson, Artur Riazanov
    Automating OBDD proofs is NP-hard.
    In Proceedings of MFCS 2022, LIPIcs vol. 241, pp. 59:1-59:15. [doi]

  • Dmitry Itsykson, Artur Riazanov and Petr Smirnov
    Tight Bounds for Tseitin Formulas.
    In Proceedings of SAT 2022, LIPIcs vol. 236, pp. 6:1-6:21. [doi]

  • Dmitry Itsykson, Artur Riazanov
    Proof complexity of natural formulas via communication arguments.
    ECCC Report TR20-184. In Proceedings of Computational Complexity Conference 2021, LIPIcs vol. 200, 3:1-3:34, 2021.

  • Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov
    Lower Bounds on OBDD Proofs with Several Orders.
    ACM Trans. Comput. Log. 22(4): 26:1-26:30, 2021. ECCC Report TR20-73.

  • Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
    Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.
    Comput. Complex. 30(2): 13, 2021. ECCC Report TR19-178.

  • 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. Pure Appl. Log. 174(1): 103166 (2023).
    The preliminary version appeared in Proceedings of MFCS 2019, LIPIcs vol. 138, 49:1-49:15.

  • Ludmila Glinskih and Dmitry Itsykson
    On Tseitin formulas, read-once branching programs and treewidth
    ECCC Report TR19-020. Draft [pdf]. Theory Comput. Syst. 65(3): 613-633, 2021.
    The preliminary version appeared in Proceedings of CSR 2019, LNCS vol, 11532, 143--155. The paper won Yandex best paper award.

  • 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 LIPIcs. Leibniz Int. Proc. Inform., 102 16:1-16:24, 2018.

  • Dmitry Itsykson and Alexander Knop
    Hard satisfiable formulas for splittings by linear combinations
    In Proceedings of SAT 2017, LNCS 10491:53Ц61, 2017 [pdf].

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

  • Dmitry Itsykson, Alexander Knop, Andrei Romashchenko and Dmitry Sokolov
    On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables.
    J. Symb. Log. 85(2): 632-670, 2020.
    The preliminary version appeared in Proceedings of STACS 2017, LIPIcs. Leibniz Int. Proc. Inform., 66 43:1-43:14, 2017.
    Full version is available as ECCC Report TR19-001

  • Dmitry Itsykson, Alexander Okhotin and Vsevolod Oparin
    Computational and proof complexity of partial string avoidability
    ACM Trans. Comput. Theory 13(1): 6:1-6:25 (2021).
    Preliminary version appeared in proceedings of MFCS 2016 LIPIcs. Leibniz Int. Proc. Inform. 58: 51:1-51:13, 2016. [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. In Proceedings of ISAAC 2016, LIPIcs. Leibniz Int. Proc. Inform., 64 38:1-38:12, 2016.

  • Dmitry Itsykson, Alexander Knop and Dmitry Sokolov
    Heuristic time hierarchies via hierarchies for sampling distributions
    ECCC Report TR14-178 In Proceedings of ISAAC 2015, LNCS 9472: 201Ц211, 2015.

  • Dmitry Itsykson, Mikhail Slabodkin and Dmitry Sokolov
    Resolution complexity of perfect matching principles for sparse graphs
    ECCC Report TR14-093. In Proceedings of CSR 2015, LNCS 9139: 219-230, 2015. Draft [.pdf].

  • Dmitry Itsykson and Dmitry Sokolov
    Lower bounds for splittings by linear combinations.
    In Proceedings of MFCS-2014, LNCS 8635: 372-383, 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). Theory of Computing Systems, (2014) 54:261Ц276.
    Preliminary version appeared in proceedings of CSR 2010, LNCS 6072, pp. 204-215. The paper won Yandex best paper award. Draft [.pdf].

  • 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].