Dmitry Itsykson and Dmitry Sokolov
Resolution over linear equations modulo two.
Accepted to Annals of Pure and Applied Logic.
doi
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
Bounded-depth Frege complexity of Tseitin formulas for all graphs
ECCC Report
TR19-020.
Sam Buss, Dmitry Itsykson, Alexander Knop and Dmitry Sokolov
Breaking Through the Reordering Obstacle in OBDD Proof Systems
Draft
[pdf].
Ludmila Glinskih, Dmitry Itsykson, Artur Riazanov and Petr Smirnov
Complexity of read-once branching programs for satisfiable and unsatisfiable Tseitin formulas
Draft
[pdf].
Ludmila Glinskih and Dmitry Itsykson
On Tseitin formulas, read-once branching programs and treewidth
ECCC Report
TR19-020.
Draft
[pdf]. Accepted to CSR 2019.
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
MFCS 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. 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].