|
|
Research papers
Edward A. Hirsch
and Dmitry Itsykson,
On an optimal randomized acceptor for graph nonisomorphism.
To appear in Information Processing Letters.
Draft [.pdf].
Dmitry Itsykson and Dmitry Sokolov
Lower bounds for myopic DPLL algorithms with a cut heuristic.
Accepted to ISAAC 2011.
Draft [.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.
To appear in Zapiski Nauchnyh Seminarov POMI (Journal of Mathematical Sciences).
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]. To appear in Theory of Computing Systems.
Dmitry Itsykson and Dmitry Sokolov
The complexity of inversion of explicit Goldreich's function by DPLL algorithms
PDMI PREPRINT 8/2010, [pdf.gz].
Accepted to CSR 2011.
To appear in Zapiski Nauchnyh Seminarov POMI (Journal of Mathematical Sciences).
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].
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].
|
