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)

Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies. - Arist Kojevnikov; Dmitry Itsykson (ICALP (1), 2006)

An infinitely-often one-way function based on an average-case assumption. - Edward A. Hirsch; Dmitry Itsykson (Electron. Colloquium Comput. Complex., 2007)

Structural complexity of AvgBPP. - Dmitry Itsykson (Electron. Colloquium Comput. Complex., 2008)

On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity. - Edward A. Hirsch; Dmitry Itsykson (STACS, 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)

The Complexity of Inversion of Explicit Goldreich's Function by DPLL Algorithms. - Dmitry Itsykson; Dmitry Sokolov 001 (CSR, 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 001 (Electron. Colloquium Comput. Complex., 2012)

On an optimal randomized acceptor for graph nonisomorphism. - Edward A. Hirsch; Dmitry Itsykson (Inf. Process. Lett., 2012)

Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP. - Dmitry Itsykson; Vsevolod Oparin (CSR, 2013)

Lower Bounds for Splittings by Linear Combinations. - Dmitry Itsykson; Dmitry Sokolov 001 (MFCS (2), 2014)

Tree-like resolution complexity of two planar problems. - Dmitry Itsykson; Anna Malova; Vsevolod Oparin; Dmitry Sokolov 001 (CoRR, 2014)

Heuristic time hierarchies via hierarchies for sampling distributions. - Dmitry Itsykson; Alexander Knop; Dmitry Sokolov 001 (Electron. Colloquium Comput. Complex., 2014)

Resolution complexity of perfect mathcing principles for sparse graphs. - Dmitry Itsykson; Mikhail Slabodkin; Dmitry Sokolov 001 (Electron. Colloquium Comput. Complex., 2014)

On Fast Heuristic Non-deterministic Algorithms and Short Heuristic Proofs. - Dmitry Itsykson; Dmitry Sokolov 001 (Fundam. Informaticae, 2014)

Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms. - Dmitry Itsykson (Theory Comput. Syst., 2014)

Resolution Complexity of Perfect Matching Principles for Sparse Graphs. - Dmitry Itsykson; Mikhail Slabodkin; Dmitry Sokolov 001 (CSR, 2015)

Complexity of distributions and average-case hardness. - Dmitry Itsykson; Alexander Knop; Dmitry Sokolov 001 (Electron. Colloquium Comput. Complex., 2015)

Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles. - Dmitry Itsykson; Vsevolod Oparin; Mikhail Slabodkin; Dmitry Sokolov 001 (Fundam. Informaticae, 2016)

Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs. - Ludmila Glinskih; Dmitry Itsykson (MFCS, 2017)

Hard satisfiable formulas for splittings by linear combinations. - Dmitry Itsykson; Alexander Knop (Electron. Colloquium Comput. Complex., 2017)

Reordering Rule Makes OBDD Proof Systems Stronger. - Sam Buss; Dmitry Itsykson; Alexander Knop; Dmitry Sokolov 001 (Electron. Colloquium Comput. Complex., 2018)

Bounded-depth Frege complexity of Tseitin formulas for all graphs. - Nicola Galesi; Dmitry Itsykson; Artur Riazanov; Anastasia Sofronova (Electron. Colloquium Comput. Complex., 2019)

On Tseitin formulas, read-once branching programs and treewidth. - Ludmila Glinskih; Dmitry Itsykson (Electron. Colloquium Comput. Complex., 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)

Resolution over linear equations modulo two. - Dmitry Itsykson; Dmitry Sokolov 001 (Ann. Pure Appl. Log., 2020)

Lower Bounds on OBDD Proofs with Several Orders. - Sam Buss; Dmitry Itsykson; Alexander Knop; Artur Riazanov; Dmitry Sokolov 001 (Electron. Colloquium Comput. Complex., 2020)

Computational and proof complexity of partial string avoidability. - Dmitry Itsykson; Alexander Okhotin; Vsevolod Oparin (Electron. Colloquium Comput. Complex., 2020)

Proof complexity of natural formulas via communication arguments. - Dmitry Itsykson; Artur Riazanov (Electron. Colloquium Comput. Complex., 2020)

On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables. - Dmitry Itsykson; Alexander Knop; Andrei E. Romashchenko; Dmitry Sokolov 001 (J. Symb. Log., 2020)

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)

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)

Tight Bounds for Tseitin Formulas. - Dmitry Itsykson; Artur Riazanov; Petr Smirnov (SAT, 2022)

Automating OBDD proofs is NP-hard. - Dmitry Itsykson; Artur Riazanov (Electron. Colloquium Comput. Complex., 2022)

Lower bounds for regular resolution over parities. - Klim Efremenko; Michal Garlík; Dmitry Itsykson (Electron. Colloquium Comput. Complex., 2023)

On Limits of Symbolic Approach to SAT Solving. - Dmitry Itsykson; Sergei Ovcharov (SAT, 2024)

Lifting to regular resolution over parities via games. - Yaroslav Alekseev; Dmitry Itsykson (Electron. Colloquium Comput. Complex., 2024)

Lifting to Bounded-Depth and Regular Resolutions over Parities via Games. - Yaroslav Alekseev; Dmitry Itsykson (STOC, 2025)

Amortized Closure and Its Applications in Lifting for Resolution over Parities. - Klim Efremenko; Dmitry Itsykson (Electron. Colloquium Comput. Complex., 2025)

Supercritical Tradeoff Between Size and Depth for Resolution over Parities. - Dmitry Itsykson; Alexander Knop (Electron. Colloquium Comput. Complex., 2025)