Dmitry Itsykson

71 papers A* 3A 9B 7C 1Misc 6Journal 43Unranked 2
YearRankTypeTitle / Venue / Authors
2026 J jnl
Resolution Width Lifts to Near-Quadratic-Depth Res(⊕) Size.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Vladimir Podolskii, Alexander Shekhovtsov
2026 A conf
Supercritical Tradeoff Between Size and Depth for Resolution over Parities.
ITCS
Dmitry Itsykson, Alexander Knop
2025 A conf
Amortized Closure and Its Applications in Lifting for Resolution over Parities.
CCC
Klim Efremenko, Dmitry Itsykson
2025 J jnl
Amortized Closure and Its Applications in Lifting for Resolution over Parities.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Dmitry Itsykson
2025 A* conf
Lifting to Bounded-Depth and Regular Resolutions over Parities via Games.
STOC
Yaroslav Alekseev, Dmitry Itsykson
2025 J jnl
Lower Bounds for Regular Resolution over Parities.
SIAM J. Comput.
Klim Efremenko, Michal Garlík, Dmitry Itsykson
2025 J jnl
Strong ETH Holds for Bounded-Depth Resolution over Parities.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Dmitry Itsykson
2025 J jnl
Supercritical Tradeoff Between Size and Depth for Resolution over Parities.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Alexander Knop
2024 J jnl
Lifting to regular resolution over parities via games.
Electron. Colloquium Comput. Complex.
Yaroslav Alekseev, Dmitry Itsykson
2024 A* conf
Lower Bounds for Regular Resolution over Parities.
STOC
Klim Efremenko, Michal Garlík, Dmitry Itsykson
2024 A conf
On Limits of Symbolic Approach to SAT Solving.
SAT
Dmitry Itsykson, Sergei Ovcharov
2023 J jnl
Bounded-depth Frege complexity of Tseitin formulas for all graphs.
Ann. Pure Appl. Log.
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
2023 J jnl
Lower bounds for regular resolution over parities.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Michal Garlík, Dmitry Itsykson
2022 B conf
Automating OBDD proofs is NP-hard.
MFCS
Dmitry Itsykson, Artur Riazanov
2022 J jnl
Automating OBDD proofs is NP-hard.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Artur Riazanov
2022 A conf
Tight Bounds for Tseitin Formulas.
SAT
Dmitry Itsykson, Artur Riazanov, Petr Smirnov
2021 J jnl
Computational and Proof Complexity of Partial String Avoidability.
ACM Trans. Comput. Theory
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
2021 J jnl
Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.
Comput. Complex.
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
2021 J jnl
Lower Bounds on OBDD Proofs with Several Orders.
ACM Trans. Comput. Log.
Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov
2021 J jnl
Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.
Comput. Complex.
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
2021 J jnl
On Tseitin Formulas, Read-Once Branching Programs and Treewidth.
Theory Comput. Syst.
Ludmila Glinskih, Dmitry Itsykson
2021 A conf
Proof Complexity of Natural Formulas via Communication Arguments.
CCC
Dmitry Itsykson, Artur Riazanov
2020 J jnl
Computational and proof complexity of partial string avoidability.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
2020 J jnl
Lower Bounds on OBDD Proofs with Several Orders.
Electron. Colloquium Comput. Complex.
Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov
2020 J jnl
On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables.
J. Symb. Log.
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov
2020 J jnl
Proof complexity of natural formulas via communication arguments.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Artur Riazanov
2020 J jnl
Resolution over linear equations modulo two.
Ann. Pure Appl. Log.
Dmitry Itsykson, Dmitry Sokolov
2019 J jnl
Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
2019 B conf
Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs.
MFCS
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
2019 J jnl
Bounded-depth Frege complexity of Tseitin formulas for all graphs.
Electron. Colloquium Comput. Complex.
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
2019 J jnl
On OBDD-based algorithms and proof systems that dynamically change order of variables.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov
2019 Misc conf
On Tseitin Formulas, Read-Once Branching Programs and Treewidth.
CSR
Ludmila Glinskih, Dmitry Itsykson
2019 J jnl
On Tseitin formulas, read-once branching programs and treewidth.
Electron. Colloquium Comput. Complex.
Ludmila Glinskih, Dmitry Itsykson
2018 A conf
Reordering Rule Makes OBDD Proof Systems Stronger.
CCC
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
2018 J jnl
Reordering Rule Makes OBDD Proof Systems Stronger.
Electron. Colloquium Comput. Complex.
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
2017 A conf
Hard Satisfiable Formulas for Splittings by Linear Combinations.
SAT
Dmitry Itsykson, Alexander Knop
2017 J jnl
Hard satisfiable formulas for splittings by linear combinations.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Alexander Knop
2017 A conf
On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables.
STACS
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov
2017 B conf
Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.
MFCS
Ludmila Glinskih, Dmitry Itsykson
2016 B conf
Complexity of Distributions and Average-Case Hardness.
ISAAC
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
2016 B conf
Computational and Proof Complexity of Partial String Avoidability.
MFCS
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
2016 J jnl
Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles.
Fundam. Informaticae
Dmitry Itsykson, Vsevolod Oparin, Mikhail Slabodkin, Dmitry Sokolov
2015 J jnl
Complexity of distributions and average-case hardness.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
2015 B conf
Heuristic Time Hierarchies via Hierarchies for Sampling Distributions.
ISAAC
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
2015 Misc conf
Resolution Complexity of Perfect Matching Principles for Sparse Graphs.
CSR
Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov
2014 J jnl
Heuristic time hierarchies via hierarchies for sampling distributions.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
2014 J jnl
Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms.
Theory Comput. Syst.
Dmitry Itsykson
2014 — conf
Lower Bounds for Splittings by Linear Combinations.
MFCS (2)
Dmitry Itsykson, Dmitry Sokolov
2014 J jnl
On Fast Heuristic Non-deterministic Algorithms and Short Heuristic Proofs.
Fundam. Informaticae
Dmitry Itsykson, Dmitry Sokolov
2014 J jnl
Resolution complexity of perfect mathcing principles for sparse graphs.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov
2014 J jnl
Tree-like resolution complexity of two planar problems.
CoRR
Dmitry Itsykson, Anna Malova, Vsevolod Oparin, Dmitry Sokolov
2013 Misc conf
Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP.
CSR
Dmitry Itsykson, Vsevolod Oparin
2012 J jnl
Lower bounds for myopic DPLL algorithms with a cut heuristic.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Dmitry Sokolov
2012 J jnl
On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography.
Theory Comput. Syst.
Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal
2012 J jnl
On an optimal randomized acceptor for graph nonisomorphism.
Inf. Process. Lett.
Edward A. Hirsch, Dmitry Itsykson
2011 B conf
Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic.
ISAAC
Dmitry Itsykson, Dmitry Sokolov
2011 J jnl
Optimal heuristic algorithms for the image of an injective function.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal
2011 Misc conf
The Complexity of Inversion of Explicit Goldreich's Function by DPLL Algorithms.
CSR
Dmitry Itsykson, Dmitry Sokolov
2010 Misc conf
Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms.
CSR
Dmitry Itsykson
2010 A conf
On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity.
STACS
Edward A. Hirsch, Dmitry Itsykson
2010 J jnl
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal
2010 J jnl
Structural complexity of AvgBPP.
Ann. Pure Appl. Log.
Dmitry Itsykson
2009 J jnl
On optimal heuristic randomized semidecision procedures, with application to proof complexity
CoRR
Edward A. Hirsch, Dmitry Itsykson
2009 Misc conf
Structural Complexity of AvgBPP.
CSR
Dmitry Itsykson
2008 C conf
An Infinitely-Often One-Way Function Based on an Average-Case Assumption.
WoLLIC
Edward A. Hirsch, Dmitry Itsykson
2008 J jnl
Structural complexity of AvgBPP.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson
2007 J jnl
An infinitely-often one-way function based on an average-case assumption.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Dmitry Itsykson
2006 — conf
Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies.
ICALP (1)
Arist Kojevnikov, Dmitry Itsykson
2005 J jnl
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas.
J. Autom. Reason.
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
2004 A* conf
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas.
ICALP
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
2004 J jnl
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
Electron. Colloquium Comput. Complex.
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson