Подписаться
Dmitry Itsykson
Dmitry Itsykson
Steklov Institute of Mathematics at St. Petersburg
Подтвержден адрес электронной почты в домене pdmi.ras.ru - Главная страница
Название
Процитировано
Процитировано
Год
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
892006
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
Resolution over linear equations modulo two
D Itsykson, D Sokolov
Annals of Pure and Applied Logic 171 (1), 102722, 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
252004
Lower bounds of static Lovasz-Schrijver calculus proofs for Tseitin tautologies
A Kojevnikov, D Itsykson
International Colloquium on Automata, Languages, and Programming, 323-334, 2006
222006
Reordering rule makes OBDD proof systems stronger
S Buss, D Itsykson, A Knop, D Sokolov
33rd Computational Complexity Conference (CCC 2018), 16: 1-16: 24, 2018
212018
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
182019
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
182017
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
On optimal heuristic randomized semidecision procedures, with application to proof complexity
EA Hirsch, D Itsykson
arXiv preprint arXiv:0908.2707, 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
Structural complexity of AvgBPP
D Itsykson
International Computer Science Symposium in Russia, 155-166, 2009
142009
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
102021
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
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
102005
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), 3: 1-3: 34, 2021
82021
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
82016
В данный момент система не может выполнить эту операцию. Повторите попытку позднее.
Статьи 1–20