Dmitry Itsykson

According to our database, Dmitry Itsykson authored at least 41 papers between 2004 and 2025.

Collaborative distances:

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

2025

Supercritical Tradeoff Between Size and Depth for Resolution over Parities.

Dmitry Itsykson, Alexander Knop

Electron. Colloquium Comput. Complex., 2025

Lifting to Bounded-Depth and Regular Resolutions over Parities via Games.

Yaroslav Alekseev, Dmitry Itsykson

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Amortized Closure and Its Applications in Lifting for Resolution over Parities.

Klim Efremenko, Dmitry Itsykson

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Lifting to regular resolution over parities via games.

Yaroslav Alekseev, Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2024

Lower Bounds for Regular Resolution over Parities.

Klim Efremenko, Michal Garlík, Dmitry Itsykson

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

On Limits of Symbolic Approach to SAT Solving.

Dmitry Itsykson, Sergei Ovcharov

Proceedings of the 27th International Conference on Theory and Applications of Satisfiability Testing, 2024

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

Automating OBDD proofs is NP-hard.

Dmitry Itsykson, Artur Riazanov

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

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

Proof Complexity of Natural Formulas via Communication Arguments.

Dmitry Itsykson, Artur Riazanov

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Lower Bounds on OBDD Proofs with Several Orders.

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

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

Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs.

Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

On Tseitin Formulas, Read-Once Branching Programs and Treewidth.

Ludmila Glinskih, Dmitry Itsykson

Proceedings of the Computer Science - Theory and Applications, 2019

2018

Reordering Rule Makes OBDD Proof Systems Stronger.

Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables.

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

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Hard Satisfiable Formulas for Splittings by Linear Combinations.

Dmitry Itsykson, Alexander Knop

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28, 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

Computational and Proof Complexity of Partial String Avoidability.

Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Complexity of Distributions and Average-Case Hardness.

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

2015

Heuristic Time Hierarchies via Hierarchies for Sampling Distributions.

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Proceedings of the Algorithms and Computation - 26th International Symposium, 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

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

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 Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography.

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

Theory Comput. Syst., 2012

On an optimal randomized acceptor for graph nonisomorphism.

Edward A. Hirsch, Dmitry Itsykson

Inf. Process. Lett., 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

Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic.

Dmitry Itsykson, Dmitry Sokolov

Proceedings of the Algorithms and Computation - 22nd International Symposium, 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 Application to Proof Complexity.

Edward A. Hirsch, Dmitry Itsykson

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

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

Dmitry Itsykson

Proceedings of the Computer Science, 2010

2009

Structural Complexity of AvgBPP.

Dmitry Itsykson

Proceedings of the Computer Science, 2009

2008

An Infinitely-Often One-Way Function Based on an Average-Case Assumption.

Edward A. Hirsch, Dmitry Itsykson

Proceedings of the Logic, 2008

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

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004