Dmitry Itsykson

According to our database, Dmitry Itsykson authored at least 36 papers between 2004 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

Lower bounds for regular resolution over parities.

Klim Efremenko, Michal Garlík, Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2023

2022

Automating OBDD proofs is NP-hard.

Dmitry Itsykson, Artur Riazanov

Electron. Colloquium Comput. Complex., 2022

Tight Bounds for Tseitin Formulas.

Dmitry Itsykson, Artur Riazanov, Petr Smirnov

Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing, 2022

2021

Lower Bounds on OBDD Proofs with Several Orders.

Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov

ACM Trans. Comput. Log., 2021

Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.

Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov

Comput. Complex., 2021

Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.

Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov

Comput. Complex., 2021

2020

On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables.

Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov

J. Symb. Log., 2020

Proof complexity of natural formulas via communication arguments.

Dmitry Itsykson, Artur Riazanov

Electron. Colloquium Comput. Complex., 2020

Computational and proof complexity of partial string avoidability.

Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

Electron. Colloquium Comput. Complex., 2020

Resolution over linear equations modulo two.

Dmitry Itsykson, Dmitry Sokolov

Ann. Pure Appl. Log., 2020

2019

Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.

Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov

Electron. Colloquium Comput. Complex., 2019

On Tseitin formulas, read-once branching programs and treewidth.

Ludmila Glinskih, Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2019

Bounded-depth Frege complexity of Tseitin formulas for all graphs.

Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova

Electron. Colloquium Comput. Complex., 2019

2018

Reordering Rule Makes OBDD Proof Systems Stronger.

Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2018

2017

Hard satisfiable formulas for splittings by linear combinations.

Dmitry Itsykson, Alexander Knop

Electron. Colloquium Comput. Complex., 2017

Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.

Ludmila Glinskih, Dmitry Itsykson

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016

Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles.

Dmitry Itsykson, Vsevolod Oparin, Mikhail Slabodkin, Dmitry Sokolov

Fundam. Informaticae, 2016

2015

Complexity of distributions and average-case hardness.

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2015

Resolution Complexity of Perfect Matching Principles for Sparse Graphs.

Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

Proceedings of the Computer Science - Theory and Applications, 2015

2014

Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms.

Dmitry Itsykson

Theory Comput. Syst., 2014

On Fast Heuristic Non-deterministic Algorithms and Short Heuristic Proofs.

Dmitry Itsykson, Dmitry Sokolov

Fundam. Informaticae, 2014

Resolution complexity of perfect mathcing principles for sparse graphs.

Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2014

Heuristic time hierarchies via hierarchies for sampling distributions.

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2014

Tree-like resolution complexity of two planar problems.

Dmitry Itsykson, Anna Malova, Vsevolod Oparin, Dmitry Sokolov

CoRR, 2014

Lower Bounds for Splittings by Linear Combinations.

Dmitry Itsykson, Dmitry Sokolov

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP.

Dmitry Itsykson, Vsevolod Oparin

Proceedings of the Computer Science - Theory and Applications, 2013

2012

On an optimal randomized acceptor for graph nonisomorphism.

Edward A. Hirsch, Dmitry Itsykson

Inf. Process. Lett., 2012

Lower bounds for myopic DPLL algorithms with a cut heuristic.

Dmitry Itsykson, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2012

2011

Optimal heuristic algorithms for the image of an injective function.

Edward A. Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal

Electron. Colloquium Comput. Complex., 2011

The Complexity of Inversion of Explicit Goldreich's Function by DPLL Algorithms.

Dmitry Itsykson, Dmitry Sokolov

Proceedings of the Computer Science - Theory and Applications, 2011

2010

On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography.

Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

Electron. Colloquium Comput. Complex., 2010

On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity.

Edward A. Hirsch, Dmitry Itsykson

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2008

Structural complexity of AvgBPP.

Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2008

2007

An infinitely-often one-way function based on an average-case assumption.

Edward A. Hirsch, Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2007

2006

Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies.

Arist Kojevnikov, Dmitry Itsykson

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2004

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2004