Follow
Dmitry Itsykson
Dmitry Itsykson
Steklov Institute of Mathematics at St. Petersburg
Verified email at pdmi.ras.ru
Title
Cited by
Cited by
Year
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
M Alekhnovich, EA Hirsch, D Itsykson
SAT 2005: Satisfiability Research in the Year 2005, 51-72, 2006
882006
On obdd-based algorithms and proof systems that dynamically change the order of variables
D Itsykson, A Knop, A Romashchenko, D Sokolov
The Journal of Symbolic Logic 85 (2), 632-670, 2020
262020
Lower bounds for splittings by linear combinations
D Itsykson, D Sokolov
International Symposium on Mathematical Foundations of Computer Science, 372-383, 2014
262014
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
M Alekhnovich, EA Hirsch, D Itsykson
Automata, Languages and Programming: 31st International Colloquium, ICALP …, 2004
232004
Reordering rule makes OBDD proof systems stronger
S Buss, D Itsykson, A Knop, D Sokolov
33rd Computational Complexity Conference (CCC 2018), 2018
222018
Lower bounds of static Lovasz-Schrijver calculus proofs for Tseitin tautologies
A Kojevnikov, D Itsykson
Automata, Languages and Programming: 33rd International Colloquium, ICALP …, 2006
222006
Lower bound on average-case complexity of inversion of goldreich’s function by drunken backtracking algorithms
D Itsykson
Computer Science–Theory and Applications: 5th International Computer Science …, 2010
192010
Resolution over linear equations modulo two
D Itsykson, D Sokolov
Annals of Pure and Applied Logic 171 (1), 102722, 2020
182020
Bounded-depth frege complexity of tseitin formulas for all graphs
N Galesi, D Itsykson, A Riazanov, A Sofronova
44th International Symposium on Mathematical Foundations of Computer Science …, 2019
162019
On optimal heuristic randomized semidecision procedures, with application to proof complexity
EA Hirsch, D Itsykson
arXiv preprint arXiv:0908.2707, 2009
162009
Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
L Glinskih, D Itsykson
42nd International Symposium on Mathematical Foundations of Computer Science …, 2017
152017
Structural complexity of AvgBPP
D Itsykson
International Computer Science Symposium in Russia, 155-166, 2009
152009
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
EA Hirsch, D Itsykson, I Monakhov, A Smal
Theory of Computing Systems 51 (2), 179-195, 2012
142012
On Tseitin formulas, read-once branching programs and treewidth
L Glinskih, D Itsykson
Computer Science–Theory and Applications: 14th International Computer …, 2019
132019
Report on the mixed boolean-algebraic solver
E Hirsch, D Itsykson, A Kojevnikov, A Kulikov, S Nikolenko
Technical report, Laboratory of Mathematical Logic of St. Petersburg …, 2005
112005
Lower bounds of static Lovász-Schrijver calculus proofs for Tseitin tautologies
D Itsykson, A Kojevnikov
Zapiski Nauchnyh Seminarov POMI 340, 10-32, 2006
102006
Lower bounds for myopic DPLL algorithms with a cut heuristic
D Itsykson, D Sokolov
Algorithms and Computation: 22nd International Symposium, ISAAC 2011 …, 2011
82011
Tight lower bounds on the resolution complexity of perfect matching principles
D Itsykson, V Oparin, M Slabodkin, D Sokolov
Fundamenta Informaticae 145 (3), 229-242, 2016
72016
Graph expansion, tseitin formulas and resolution proofs for CSP
D Itsykson, V Oparin
International Computer Science Symposium in Russia, 162-173, 2013
72013
Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
D Itsykson, A Riazanov, D Sagunov, P Smirnov
computational complexity 30 (2), 13, 2021
52021
The system can't perform the operation now. Try again later.
Articles 1–20