
Research papers
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
Computational and proof complexity of partial string avoidability
MFCS 2016, [pdf].
Dmitry Itsykson, Vsevolod Oparin, Mikhail Slabodkin, Dmitriy Sokolov
Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles
Fundamenta Informaticae vol. 145, no. 3, pp. 229242, 2016.
Dmitry Itsykson, Alexander Knop and Dmitry Sokolov
Complexity of distributions and averagecase hardness
ECCC Report
TR15174. Accepted to ISAAC 2016.
Dmitry Itsykson, Alexander Knop and Dmitry Sokolov
Heuristic time hierarchies via hierarchies for sampling distributions
ECCC Report
TR14178 Accepted to ISAAC 2015.
Dmitry Itsykson, Mikhail Slabodkin and Dmitry Sokolov
Resolution complexity of perfect matching principles for
sparse graphs
ECCC Report
TR14093. Accepted to CSR 2015.
Draft [.pdf].
Dmitry Itsykson and Dmitry Sokolov
Lower bounds for splittings by linear combinations.
Accepted to MFCS2014.
Draft (updated 09.08.2014).
Dmitry Itsykson and Dmitry Sokolov
On fast nondeterministic algorithms and short heuristic proofs.
Fundamenta Informaticae, 132(1):113129, 2014.
Draft [.pdf].
Dmitry Itsykson and Vsevolod Oparin
Graph expansion, Tseitin formulas and resolution proofs for CSP.
In proceedings of CSR 2013, LNCS 7913: 162173.
Draft [.pdf].
Edward A. Hirsch
and Dmitry Itsykson,
On an optimal randomized acceptor for graph nonisomorphism.
Information Processing Letters, 112: 166171, 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 TR12141.
[pdf]
Edward A. Hirsch
, Dmitry Itsykson, Valeria Nikolaenko and Alexander Smal
Optimal heuristic algorithms for the image of an injective function
ECCC Report TR11091.
Zapiski Nauchnyh Seminarov POMI (Journal of Mathematical Sciences), 399:1532, 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 TR10193.
[pdf]. Theory of Computing Systems 51:179195, 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:88109, 2012 [pdf].
Preliminary version appeared in proceedings of CSR 2011, LNCS 6651 pp. 134147.
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.453464.
Dmitry M. Itsykson,
Lower bound on averagecase 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. 204215. 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 TR08073,
[ps],
[pdf].
Annals of Pure and Applied Logic, 162(3): 213223, 2010.
Preliminary version
appeared in proceedings of CSR 2009, LNCS 5675, pp. 155166, 2009.
The paper won Yandex best student paper award.
Edward A. Hirsch
and Dmitry M. Itsykson,
An infinitelyoften oneway function based on an averagecase assumption.
ECCC Report TR07117.
[ps]
,
[pdf]
Algebra and Analisys, 21(3):129143, 2009.
English translation: St. Petersburg Mathematical Journal, 21(3): 459468, 2010.
Preliminary version appeared in proceedings of WoLLIC 2008, LNCS 5110, pp. 208217.
Dmitry Itsykson and Arist
Kojevnikov,
Lower bounds of static LovaszSchrijver calculus proofs for Tseitin tautologies
Zapiski Nauchnyh Seminarov POMI, 340:1032, 2006 (in Russian),
[ps.gz].
English translation appeared in Journal of Mathematical Sciences
145(3):49424952, 2007,
[pdf].
Preliminary version
appeared as Exponential Lower Bound on the Size
of Static LovaszSchrijver Calculus
in Proceedings of the 33rd International Colloquium on
Automata, Languages and Programming (ICALP 2006), pp. 323334,
[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.8496. Full article appeared in Journal of Automated
Reasoning (2005) 35: 5172,
[ps],
[pdf].
