Follow
Dmitry Itsykson
Dmitry Itsykson
Steklov Institute of Mathematics at St. Petersburg
Verified email at pdmi.ras.ru - Homepage
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
902006
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
272020
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
252004
Resolution over linear equations modulo two
D Itsykson, D Sokolov
Annals of Pure and Applied Logic 171 (1), 102722, 2020
242020
Reordering rule makes OBDD proof systems stronger
S Buss, D Itsykson, A Knop, D Sokolov
33rd Computational Complexity Conference (CCC 2018), 2018
232018
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
202010
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
172019
On optimal heuristic randomized semidecision procedures, with application to proof complexity
EA Hirsch, D Itsykson
arXiv preprint arXiv:0908.2707, 2009
172009
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
162017
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
152012
Structural complexity of AvgBPP
D Itsykson
International Computer Science Symposium in Russia, 155-166, 2009
152009
On Tseitin formulas, read-once branching programs and treewidth
L Glinskih, D Itsykson
Computer Science–Theory and Applications: 14th International Computer …, 2019
142019
Lower bounds of static Lovász-Schrijver calculus proofs for Tseitin tautologies
D Itsykson, A Kojevnikov
Zapiski Nauchnyh Seminarov POMI 340, 10-32, 2006
112006
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 for myopic DPLL algorithms with a cut heuristic
D Itsykson, D Sokolov
Algorithms and Computation: 22nd International Symposium, ISAAC 2011 …, 2011
92011
Proof complexity of natural formulas via communication arguments
D Itsykson, A Riazanov
36th Computational Complexity Conference (CCC 2021), 2021
82021
Hard satisfiable formulas for splittings by linear combinations
D Itsykson, A Knop
International Conference on Theory and Applications of Satisfiability …, 2017
72017
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
The system can't perform the operation now. Try again later.
Articles 1–20