Dmitry Itsykson

Publication Activity (10 Years)

Years Active: 2004-2024
Publications (10 Years): 33

Top Topics

Reduced Error Pruning

Top Venues

Electron. Colloquium Comput. Complex.

Fundam. Informaticae

Publications

Dmitry Itsykson, Sergei Ovcharov
On Limits of Symbolic Approach to SAT Solving. SAT (2024)
Klim Efremenko, Michal Garlík, Dmitry Itsykson
Lower Bounds for Regular Resolution over Parities. STOC (2024)
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
Bounded-depth Frege complexity of Tseitin formulas for all graphs. Ann. Pure Appl. Log. 174 (1) (2023)
Klim Efremenko, Michal Garlík, Dmitry Itsykson
Lower bounds for regular resolution over parities. Electron. Colloquium Comput. Complex. (2023)
Dmitry Itsykson, Artur Riazanov, Petr Smirnov
Tight Bounds for Tseitin Formulas. SAT (2022)
Dmitry Itsykson, Artur Riazanov
Automating OBDD proofs is NP-hard. Electron. Colloquium Comput. Complex. (2022)
Dmitry Itsykson, Artur Riazanov
Automating OBDD proofs is NP-hard. MFCS (2022)
Ludmila Glinskih, Dmitry Itsykson
On Tseitin Formulas, Read-Once Branching Programs and Treewidth. Theory Comput. Syst. 65 (3) (2021)
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
Computational and Proof Complexity of Partial String Avoidability. ACM Trans. Comput. Theory 13 (1) (2021)
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs. Comput. Complex. 30 (2) (2021)
Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov
Lower Bounds on OBDD Proofs with Several Orders. ACM Trans. Comput. Log. 22 (4) (2021)
Dmitry Itsykson, Artur Riazanov
Proof Complexity of Natural Formulas via Communication Arguments. Computational Complexity Conference (2021)
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs. Comput. Complex. 30 (2) (2021)
Dmitry Itsykson, Artur Riazanov
Proof complexity of natural formulas via communication arguments. Electron. Colloquium Comput. Complex. 27 (2020)
Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov
On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables. J. Symb. Log. 85 (2) (2020)
Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov
Lower Bounds on OBDD Proofs with Several Orders. Electron. Colloquium Comput. Complex. 27 (2020)
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
Computational and proof complexity of partial string avoidability. Electron. Colloquium Comput. Complex. 27 (2020)
Dmitry Itsykson, Dmitry Sokolov
Resolution over linear equations modulo two. Ann. Pure Appl. Log. 171 (1) (2020)
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs. MFCS (2019)
Ludmila Glinskih, Dmitry Itsykson
On Tseitin Formulas, Read-Once Branching Programs and Treewidth. CSR (2019)
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs. Electron. Colloquium Comput. Complex. 26 (2019)
Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov
On OBDD-based algorithms and proof systems that dynamically change order of variables. Electron. Colloquium Comput. Complex. 26 (2019)
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
Bounded-depth Frege complexity of Tseitin formulas for all graphs. Electron. Colloquium Comput. Complex. 26 (2019)
Ludmila Glinskih, Dmitry Itsykson
On Tseitin formulas, read-once branching programs and treewidth. Electron. Colloquium Comput. Complex. 26 (2019)
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Reordering Rule Makes OBDD Proof Systems Stronger. Computational Complexity Conference (2018)
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Reordering Rule Makes OBDD Proof Systems Stronger. Electron. Colloquium Comput. Complex. 25 (2018)
Ludmila Glinskih, Dmitry Itsykson
Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs. MFCS (2017)
Dmitry Itsykson, Alexander Knop
Hard satisfiable formulas for splittings by linear combinations. Electron. Colloquium Comput. Complex. 24 (2017)
Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov
On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables. STACS (2017)
Dmitry Itsykson, Alexander Knop
Hard Satisfiable Formulas for Splittings by Linear Combinations. SAT (2017)
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
Computational and Proof Complexity of Partial String Avoidability. MFCS (2016)
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Complexity of Distributions and Average-Case Hardness. ISAAC (2016)
Dmitry Itsykson, Vsevolod Oparin, Mikhail Slabodkin, Dmitry Sokolov
Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles. Fundam. Informaticae 145 (3) (2016)
Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov
Resolution Complexity of Perfect Matching Principles for Sparse Graphs. CSR (2015)
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Heuristic Time Hierarchies via Hierarchies for Sampling Distributions. ISAAC (2015)
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Complexity of distributions and average-case hardness. Electron. Colloquium Comput. Complex. 22 (2015)
Dmitry Itsykson, Dmitry Sokolov
Lower Bounds for Splittings by Linear Combinations. MFCS (2) (2014)
Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov
Resolution complexity of perfect mathcing principles for sparse graphs. Electron. Colloquium Comput. Complex. 21 (2014)
Dmitry Itsykson
Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms. Theory Comput. Syst. 54 (2) (2014)
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Heuristic time hierarchies via hierarchies for sampling distributions. Electron. Colloquium Comput. Complex. 21 (2014)
Dmitry Itsykson, Anna Malova, Vsevolod Oparin, Dmitry Sokolov
Tree-like resolution complexity of two planar problems. CoRR (2014)
Dmitry Itsykson, Dmitry Sokolov
On Fast Heuristic Non-deterministic Algorithms and Short Heuristic Proofs. Fundam. Informaticae 132 (1) (2014)
Dmitry Itsykson, Vsevolod Oparin
Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP. CSR (2013)
Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal
On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography. Theory Comput. Syst. 51 (2) (2012)
Dmitry Itsykson, Dmitry Sokolov
Lower bounds for myopic DPLL algorithms with a cut heuristic. Electron. Colloquium Comput. Complex. 19 (2012)
Edward A. Hirsch, Dmitry Itsykson
On an optimal randomized acceptor for graph nonisomorphism. Inf. Process. Lett. 112 (5) (2012)
Dmitry Itsykson, Dmitry Sokolov
The Complexity of Inversion of Explicit Goldreich's Function by DPLL Algorithms. CSR (2011)
Dmitry Itsykson, Dmitry Sokolov
Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic. ISAAC (2011)
Edward A. Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal
Optimal heuristic algorithms for the image of an injective function. Electron. Colloquium Comput. Complex. 18 (2011)
Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography. Electron. Colloquium Comput. Complex. 17 (2010)
Dmitry Itsykson
Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms. CSR (2010)
Edward A. Hirsch, Dmitry Itsykson
On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity. STACS (2010)
Dmitry Itsykson
Structural complexity of AvgBPP. Ann. Pure Appl. Log. 162 (3) (2010)
Edward A. Hirsch, Dmitry Itsykson
On optimal heuristic randomized semidecision procedures, with application to proof complexity CoRR (2009)
Dmitry Itsykson
Structural Complexity of AvgBPP. CSR (2009)
Edward A. Hirsch, Dmitry Itsykson
An Infinitely-Often One-Way Function Based on an Average-Case Assumption. WoLLIC (2008)
Dmitry Itsykson
Structural complexity of AvgBPP. Electron. Colloquium Comput. Complex. 15 (073) (2008)
Edward A. Hirsch, Dmitry Itsykson
An infinitely-often one-way function based on an average-case assumption. Electron. Colloquium Comput. Complex. 14 (117) (2007)
Arist Kojevnikov, Dmitry Itsykson
Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies. ICALP (1) (2006)
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. J. Autom. Reason. 35 (1-3) (2005)
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas Electron. Colloquium Comput. Complex. (041) (2004)
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. ICALP (2004)