Dmitry Sokolov

75 papers A* 8A 13B 3Misc 3Journal 47Unranked 1
YearRankTypeTitle / Venue / Authors
2026 A conf
Lower Bounds Beyond DNF of Parities.
ITCS
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2025 A conf
A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion.
CCC
Anastasia Sofronova, Dmitry Sokolov
2025 J jnl
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.
TheoretiCS
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
2025 A conf
Generalised Linial-Nisan Conjecture Is False for DNFs.
CCC
Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Generalised Linial-Nisan Conjecture is False for DNFs.
Electron. Colloquium Comput. Complex.
Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Lower Bounds Beyond DNF of Parities.
Electron. Colloquium Comput. Complex.
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2025 J jnl
Monotone Circuit Complexity of Matching.
CoRR
Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2025 J jnl
Monotone Circuit Complexity of Matching.
Electron. Colloquium Comput. Complex.
Bruno Pasqualotto Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2025 J jnl
Pseudodeterministic Communication Complexity.
CoRR
Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Pseudodeterministic Communication Complexity.
Electron. Colloquium Comput. Complex.
Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Sampling Permutations with Cell Probes is Hard.
CoRR
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov
2025 J jnl
Sampling Permutations with Cell Probes is Hard.
Electron. Colloquium Comput. Complex.
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov
2025 J jnl
Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication.
CoRR
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2025 A conf
Searching for Falsified Clause in Random (log{n})-CNFs Is Hard for Randomized Communication.
APPROX/RANDOM
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Searching for Falsified Clause in Random log{n}-CNFs is Hard for Randomized Communication.
Electron. Colloquium Comput. Complex.
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Sign-Rank of
CoRR
Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov
2025 J jnl
Sign-Rank of $k$-Hamming Distance is Constant.
Electron. Colloquium Comput. Complex.
Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov
2025 A* conf
Sign-Rank of k-Hamming Distance is Constant.
FOCS
Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov
2025 A* conf
Supercritical Tradeoffs for Monotone Circuits.
STOC
Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov
2024 A* conf
Hardness Condensation by Restriction.
STOC
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
2024 A* conf
Random (log n)-CNF Are Hard for Cutting Planes (Again).
STOC
Dmitry Sokolov
2024 J jnl
Supercritical Tradeoffs for Monotone Circuits.
CoRR
Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov
2024 J jnl
Supercritical Tradeoffs for Monotone Circuits.
Electron. Colloquium Comput. Complex.
Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov
2023 J jnl
Hardness Condensation by Restriction.
Electron. Colloquium Comput. Complex.
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
2023 J jnl
Random (log n)-CNF are Hard for Cutting Planes (Again).
Electron. Colloquium Comput. Complex.
Dmitry Sokolov
2023 A conf
Sampling and Certifying Symmetric Functions.
APPROX/RANDOM
Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov
2023 J jnl
Sampling and Certifying Symmetric Functions.
CoRR
Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov
2023 J jnl
Sampling and Certifying Symmetric Functions.
Electron. Colloquium Comput. Complex.
Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov
2023 A* conf
Top-Down Lower Bounds for Depth-Four Circuits.
FOCS
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2023 J jnl
Top-Down Lower Bounds for Depth-Four Circuits.
CoRR
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2023 J jnl
Top-Down Lower Bounds for Depth-Four Circuits.
Electron. Colloquium Comput. Complex.
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2022 J jnl
A Lower Bound for
Electron. Colloquium Comput. Complex.
Anastasia Sofronova, Dmitry Sokolov
2022 A conf
Pseudorandom Generators, Resolution and Heavy Width.
CCC
Dmitry Sokolov
2021 A* conf
Automating algebraic proof systems is NP-hard.
STOC
Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov
2021 A conf
Branching Programs with Bounded Repetitions and Flow Formulas.
CCC
Anastasia Sofronova, Dmitry Sokolov
2021 J jnl
Branching Programs with Bounded Repetitions and Flow Formulas.
Electron. Colloquium Comput. Complex.
Anastasia Sofronova, Dmitry Sokolov
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
Pseudorandom Generators, Resolution and Heavy Width.
Electron. Colloquium Comput. Complex.
Dmitry Sokolov
2021 A conf
The Power of Negative Reasoning.
CCC
Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Dmitry Sokolov
2020 J jnl
(Semi)Algebraic Proofs over ±1 Variables.
Electron. Colloquium Comput. Complex.
Dmitry Sokolov
2020 A* conf
(Semi)Algebraic proofs over ±1 variables.
STOC
Dmitry Sokolov
2020 J jnl
Automating Algebraic Proof Systems is NP-Hard.
Electron. Colloquium Comput. Complex.
Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna F. de Rezende
2020 A conf
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.
CCC
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
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
Monotone Circuit Lower Bounds from Resolution.
Theory Comput.
Ankit Garg, Mika Göös, Pritish Kamath, 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
Resolution over linear equations modulo two.
Ann. Pure Appl. Log.
Dmitry Itsykson, Dmitry Sokolov
2020 A conf
Trade-Offs Between Size and Degree in Polynomial Calculus.
ITCS
Guillaume Lagarde, Jakob Nordström, Dmitry Sokolov, Joseph Swernofsky
2019 A conf
Adventures in Monotone Complexity and TFNP.
ITCS
Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
2019 J jnl
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.
CoRR
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
2019 J jnl
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.
Electron. Colloquium Comput. Complex.
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
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
2018 J jnl
Adventures in Monotone Complexity and TFNP.
Electron. Colloquium Comput. Complex.
Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
2018 A* conf
Monotone circuit lower bounds from resolution.
STOC
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
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 Misc conf
Dag-Like Communication and Its Applications.
CSR
Dmitry Sokolov
2017 J jnl
Monotone Circuit Lower Bounds from Resolution.
Electron. Colloquium Comput. Complex.
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
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
2016 B conf
Complexity of Distributions and Average-Case Hardness.
ISAAC
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
2016 J jnl
Dag-like Communication and Its Applications.
Electron. Colloquium Comput. Complex.
Dmitry Sokolov
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 J jnl
On the probabilistic closure of the loose unambiguous hierarchy.
Inf. Process. Lett.
Edward A. Hirsch, 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 — 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
On the probabilistic closure of the loose unambiguous hierarchy.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, 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
2012 J jnl
Lower bounds for myopic DPLL algorithms with a cut heuristic.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Dmitry Sokolov
2011 B conf
Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic.
ISAAC
Dmitry Itsykson, Dmitry Sokolov
2011 Misc conf
The Complexity of Inversion of Explicit Goldreich's Function by DPLL Algorithms.
CSR
Dmitry Itsykson, Dmitry Sokolov