Dmitry Sokolov

Publication Activity (10 Years)

Years Active: 2011-2024
Publications (10 Years): 45

Top Topics

Attributed Relational Graph

Average Case Complexity

Top Venues

Electron. Colloquium Comput. Complex.

Computational Complexity Conference

Publications

Dmitry Sokolov
Random (log n)-CNF Are Hard for Cutting Planes (Again). STOC (2024)
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
Hardness Condensation by Restriction. STOC (2024)
Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov
Sampling and Certifying Symmetric Functions. APPROX/RANDOM (2023)
Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov
Sampling and Certifying Symmetric Functions. Electron. Colloquium Comput. Complex. (2023)
Dmitry Sokolov
Random (log n)-CNF are Hard for Cutting Planes (Again). Electron. Colloquium Comput. Complex. (2023)
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Top-Down Lower Bounds for Depth-Four Circuits. Electron. Colloquium Comput. Complex. (2023)
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
Hardness Condensation by Restriction. Electron. Colloquium Comput. Complex. (2023)
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Top-Down Lower Bounds for Depth-Four Circuits. CoRR (2023)
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Top-Down Lower Bounds for Depth-Four Circuits. FOCS (2023)
Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov
Sampling and Certifying Symmetric Functions. CoRR (2023)
Dmitry Sokolov
Pseudorandom Generators, Resolution and Heavy Width. CCC (2022)
Anastasia Sofronova, Dmitry Sokolov
-DNF Resolution on Random CNF Formulas via Expansion. Electron. Colloquium Comput. Complex. (2022)
Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov
Automating algebraic proof systems is NP-hard. STOC (2021)
Anastasia Sofronova, Dmitry Sokolov
Branching Programs with Bounded Repetitions and Flow Formulas. Computational Complexity Conference (2021)
Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Dmitry Sokolov
The Power of Negative Reasoning. Computational Complexity Conference (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)
Anastasia Sofronova, Dmitry Sokolov
Branching Programs with Bounded Repetitions and $\mathrm{Flow}$ Formulas. Electron. Colloquium Comput. Complex. 28 (2021)
Dmitry Sokolov
Pseudorandom Generators, Resolution and Heavy Width. Electron. Colloquium Comput. Complex. 28 (2021)
Dmitry Sokolov
(Semi)Algebraic Proofs over ±1 Variables. Electron. Colloquium Comput. Complex. 27 (2020)
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
Monotone Circuit Lower Bounds from Resolution. Theory Comput. 16 (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 Sokolov
(Semi)Algebraic proofs over ±1 variables. STOC (2020)
Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna F. de Rezende
Automating Algebraic Proof Systems is NP-Hard. Electron. Colloquium Comput. Complex. 27 (2020)
Dmitry Itsykson, Dmitry Sokolov
Resolution over linear equations modulo two. Ann. Pure Appl. Log. 171 (1) (2020)
Guillaume Lagarde, Jakob Nordström, Dmitry Sokolov, Joseph Swernofsky
Trade-Offs Between Size and Degree in Polynomial Calculus. ITCS (2020)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. Computational Complexity Conference (2020)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. CoRR (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)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. Electron. Colloquium Comput. Complex. 26 (2019)
Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
Adventures in Monotone Complexity and TFNP. ITCS (2019)
Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
Adventures in Monotone Complexity and TFNP. Electron. Colloquium Comput. Complex. 25 (2018)
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
Monotone circuit lower bounds from resolution. STOC (2018)
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)
Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov
On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables. STACS (2017)
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
Monotone Circuit Lower Bounds from Resolution. Electron. Colloquium Comput. Complex. 24 (2017)
Dmitry Sokolov
Dag-Like Communication and Its Applications. CSR (2017)
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 Sokolov
Dag-like Communication and Its Applications. Electron. Colloquium Comput. Complex. 23 (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)
Edward A. Hirsch, Dmitry Sokolov
On the probabilistic closure of the loose unambiguous hierarchy. Inf. Process. Lett. 115 (9) (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, 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)
Edward A. Hirsch, Dmitry Sokolov
On the probabilistic closure of the loose unambiguous hierarchy. Electron. Colloquium Comput. Complex. 21 (2014)
Dmitry Itsykson, Dmitry Sokolov
Lower bounds for myopic DPLL algorithms with a cut heuristic. Electron. Colloquium Comput. Complex. 19 (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)