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