Dmitry Itsykson
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Dmitry Itsykson has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Dmitry Sokolov
EPFL, Lausanne, Switzerland
8 shared publications - Alexander Knop
University of California San Diego La Jolla CA USA
2 shared publications - Artur Riazanov
Saint Petersburg Department of Steklov Institute of Mathematics of Russian Academy of Sciences, Saint Petersburg, Russia
2 shared publications - Danil Sagunov
St. Petersburg State University, St. Petersburg, Russian Federation
2 shared publications - Klim Efremenko
Ben-Gurion University of the Negev, Beer Sheva, Israel
2 shared publications - Mikhail Slabodkin
St. Petersburg Academic University, 8 Khlopina, St.Petersburg, 194021, Russia
2 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 898-909
Strong ETH Holds for Bounded-Depth Resolution over Parities
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 898-909
Open AccessStrong ETH Holds for Bounded-Depth Resolution over Parities
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 584-595
Lifting to Bounded-Depth and Regular Resolutions over Parities via Games
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 584-595
Open AccessLifting to Bounded-Depth and Regular Resolutions over Parities via Games
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 640-651
Lower Bounds for Regular Resolution over Parities
The proof system resolution over parities (Res(⊕)) operates with disjunctions of linear equations (linear clauses) over GF(2); it extends the resolution proof system by incorporating linear algebra over GF(2). Over the years, several exponential lower bounds on the size of tree-like refutations have been established. However, proving a superpolynomial lower bound on the size of dag-like Res(⊕) refutations remains a highly challenging open question. We prove an exponential lower bound for regular Res(⊕). Regular Res(⊕) is a subsystem of dag-like Res(⊕) that naturally extends regular resolution. This is the first known superpolynomial lower bound for a fragment of dag-like Res(⊕) which is exponentially stronger than tree-like Res(⊕). In the regular regime, resolving linear clauses C1 and C2 on a linear form f is permitted only if, for both i∈ {1,2}, the linear form f does not lie within the linear span of all linear forms that were used in resolution rules during the derivation of Ci. Namely, we show that the size of any regular Res(⊕) refutation of the binary pigeonhole principle BPHPnn+1 is at least 2Ω(∛n/logn). A corollary of our result is an exponential lower bound on the size of a strongly read-once linear branching program solving a search problem. This resolves an open question raised by Gryaznov, Pudlak, and Talebanfard (CCC 2022). As a byproduct of our technique, we prove that the size of any tree-like Res(⊕) refutation of the weak binary pigeonhole principle BPHPnm is at least 2Ω(n) using Prover-Delayer games. We also give a direct proof of a width lower bound: we show that any dag-like Res(⊕) refutation of BPHPnm contains a linear clause C with Ω(n) linearly independent equations.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 640-651
Open AccessLower Bounds for Regular Resolution over Parities
The proof system resolution over parities (Res(⊕)) operates with disjunctions of linear equations (linear clauses) over GF(2); it extends the resolution proof system by incorporating linear algebra over GF(2). Over the years, several exponential lower bounds on the size of tree-like refutations have been established. However, proving a superpolynomial lower bound on the size of dag-like Res(⊕) refutations remains a highly challenging open question. We prove an exponential lower bound for regular Res(⊕). Regular Res(⊕) is a subsystem of dag-like Res(⊕) that naturally extends regular resolution. This is the first known superpolynomial lower bound for a fragment of dag-like Res(⊕) which is exponentially stronger than tree-like Res(⊕). In the regular regime, resolving linear clauses C1 and C2 on a linear form f is permitted only if, for both i∈ {1,2}, the linear form f does not lie within the linear span of all linear forms that were used in resolution rules during the derivation of Ci. Namely, we show that the size of any regular Res(⊕) refutation of the binary pigeonhole principle BPHPnn+1 is at least 2Ω(∛n/logn). A corollary of our result is an exponential lower bound on the size of a strongly read-once linear branching program solving a search problem. This resolves an open question raised by Gryaznov, Pudlak, and Talebanfard (CCC 2022). As a byproduct of our technique, we prove that the size of any tree-like Res(⊕) refutation of the weak binary pigeonhole principle BPHPnm is at least 2Ω(n) using Prover-Delayer games. We also give a direct proof of a width lower bound: we show that any dag-like Res(⊕) refutation of BPHPnm contains a linear clause C with Ω(n) linearly independent equations.
- 17 November 2021
- Published by Springer Nature in computational complexity
- Vol. 30 (2) , 1-2
Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
- 17 November 2021
- Published by Springer Nature in computational complexity
- Vol. 30 (2) , 1-2
Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
- Open Access
- 8 September 2021
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 22 (4) , 1-30
Lower Bounds on OBDD Proofs with Several Orders
This article is motivated by seeking lower bounds on OBDD(∧, w, r) refutations, namely, OBDD refutations that allow weakening and arbitrary reorderings. We first work with 1 - NBP ∧ refutations based on read-once nondeterministic branching programs. These generalize OBDD(∧, r) refutations. There are polynomial size 1 - NBP(∧) refutations of the pigeonhole principle, hence 1-NBP(∧) is strictly stronger than OBDD}(∧, r). There are also formulas that have polynomial size tree-like resolution refutations but require exponential size 1-NBP(∧) refutations. As a corollary, OBDD}(∧, r) does not simulate tree-like resolution, answering a previously open question. The system 1-NBP(∧, ∃) uses projection inferences instead of weakening. 1-NBP(∧, ∃ k is the system restricted to projection on at most k distinct variables. We construct explicit constant degree graphs G n on n vertices and an ε > 0, such that 1-NBP(∧, ∃ ε n ) refutations of the Tseitin formula for G n require exponential size. Second, we study the proof system OBDD}(∧, w, r ℓ ), which allows ℓ different variable orders in a refutation. We prove an exponential lower bound on the complexity of tree-like OBDD(∧, w, r ℓ ) refutations for ℓ = ε log n , where n is the number of variables and ε > 0 is a constant. The lower bound is based on multiparty communication complexity.
- 8 September 2021
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 22 (4) , 1-30
Open AccessLower Bounds on OBDD Proofs with Several Orders
This article is motivated by seeking lower bounds on OBDD(∧, w, r) refutations, namely, OBDD refutations that allow weakening and arbitrary reorderings. We first work with 1 - NBP ∧ refutations based on read-once nondeterministic branching programs. These generalize OBDD(∧, r) refutations. There are polynomial size 1 - NBP(∧) refutations of the pigeonhole principle, hence 1-NBP(∧) is strictly stronger than OBDD}(∧, r). There are also formulas that have polynomial size tree-like resolution refutations but require exponential size 1-NBP(∧) refutations. As a corollary, OBDD}(∧, r) does not simulate tree-like resolution, answering a previously open question. The system 1-NBP(∧, ∃) uses projection inferences instead of weakening. 1-NBP(∧, ∃ k is the system restricted to projection on at most k distinct variables. We construct explicit constant degree graphs G n on n vertices and an ε > 0, such that 1-NBP(∧, ∃ ε n ) refutations of the Tseitin formula for G n require exponential size. Second, we study the proof system OBDD}(∧, w, r ℓ ), which allows ℓ different variable orders in a refutation. We prove an exponential lower bound on the complexity of tree-like OBDD(∧, w, r ℓ ) refutations for ℓ = ε log n , where n is the number of variables and ε > 0 is a constant. The lower bound is based on multiparty communication complexity.
- 27 August 2021
- Published by Springer Nature in computational complexity
- Vol. 30 (2) , 1-74
Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
- 27 August 2021
- Published by Springer Nature in computational complexity
- Vol. 30 (2) , 1-74
Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
- 9 October 2020
- Published by Springer Nature in Theory of Computing Systems
- Vol. 65 (3) , 613-633
On Tseitin Formulas, Read-Once Branching Programs and Treewidth
- 9 October 2020
- Published by Springer Nature in Theory of Computing Systems
- Vol. 65 (3) , 613-633
On Tseitin Formulas, Read-Once Branching Programs and Treewidth
- Open Access
- 22 June 2020
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 85 (2) , 632-670
ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
- 22 June 2020
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 85 (2) , 632-670
Open AccessON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
- 1 January 2020
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 171 (1)
Resolution over linear equations modulo two
- 1 January 2020
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 171 (1)
Resolution over linear equations modulo two
- 16 May 2019
- Published by Springer Nature
- p. 143-155
On Tseitin Formulas, Read-Once Branching Programs and Treewidth
- 16 May 2019
- Published by Springer Nature
- p. 143-155
On Tseitin Formulas, Read-Once Branching Programs and Treewidth