Dmitry Sokolov

According to our database, Dmitry Sokolov authored at least 38 papers between 2011 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Sign-Rank of <i>k</i>-Hamming Distance is Constant.

Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov

CoRR, June, 2025

Lower Bounds Beyond DNF of Parities.

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2025

Sign-Rank of $k$-Hamming Distance is Constant.

Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2025

Monotone Circuit Complexity of Matching.

Bruno Pasqualotto Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2025

Supercritical Tradeoffs for Monotone Circuits.

Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion.

Anastasia Sofronova, Dmitry Sokolov

Proceedings of the 40th Computational Complexity Conference, 2025

Generalised Linial-Nisan Conjecture Is False for DNFs.

Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan

Proceedings of the 40th Computational Complexity Conference, 2025

Searching for Falsified Clause in Random (log{n})-CNFs Is Hard for Randomized Communication.

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan

Proceedings of the Approximation, 2025

2024

Hardness Condensation by Restriction.

Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Random (log n)-CNF Are Hard for Cutting Planes (Again).

Dmitry Sokolov

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

Top-Down Lower Bounds for Depth-Four Circuits.

Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Sampling and Certifying Symmetric Functions.

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov

Proceedings of the Approximation, 2023

2022

A Lower Bound for <i>k</i>-DNF Resolution on Random CNF Formulas via Expansion.

Anastasia Sofronova, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2022

Pseudorandom Generators, Resolution and Heavy Width.

Dmitry Sokolov

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Automating algebraic proof systems is NP-hard.

Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Branching Programs with Bounded Repetitions and Flow Formulas.

Anastasia Sofronova, Dmitry Sokolov

Proceedings of the 36th Computational Complexity Conference, 2021

The Power of Negative Reasoning.

Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Dmitry Sokolov

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Lower Bounds on OBDD Proofs with Several Orders.

Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2020

Resolution over linear equations modulo two.

Dmitry Itsykson, Dmitry Sokolov

Ann. Pure Appl. Log., 2020

(Semi)Algebraic proofs over ±1 variables.

Dmitry Sokolov

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Trade-Offs Between Size and Degree in Polynomial Calculus.

Guillaume Lagarde, Jakob Nordström, Dmitry Sokolov, Joseph Swernofsky

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.

Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Adventures in Monotone Complexity and TFNP.

Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

Monotone circuit lower bounds from resolution.

Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Reordering Rule Makes OBDD Proof Systems Stronger.

Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables.

Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Dag-Like Communication and Its Applications.

Dmitry Sokolov

Proceedings of the Computer Science - Theory and Applications, 2017

2016

Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles.

Dmitry Itsykson, Vsevolod Oparin, Mikhail Slabodkin, Dmitry Sokolov

Fundam. Informaticae, 2016

Complexity of Distributions and Average-Case Hardness.

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

2015

Heuristic Time Hierarchies via Hierarchies for Sampling Distributions.

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Resolution Complexity of Perfect Matching Principles for Sparse Graphs.

Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

Proceedings of the Computer Science - Theory and Applications, 2015

2014

On Fast Heuristic Non-deterministic Algorithms and Short Heuristic Proofs.

Dmitry Itsykson, Dmitry Sokolov

Fundam. Informaticae, 2014

Resolution complexity of perfect mathcing principles for sparse graphs.

Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2014

On the probabilistic closure of the loose unambiguous hierarchy.

Edward A. Hirsch, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2014

Tree-like resolution complexity of two planar problems.

Dmitry Itsykson, Anna Malova, Vsevolod Oparin, Dmitry Sokolov

CoRR, 2014

Lower Bounds for Splittings by Linear Combinations.

Dmitry Itsykson, Dmitry Sokolov

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2011

Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic.

Dmitry Itsykson, Dmitry Sokolov

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

The Complexity of Inversion of Explicit Goldreich's Function by DPLL Algorithms.

Dmitry Itsykson, Dmitry Sokolov

Proceedings of the Computer Science - Theory and Applications, 2011