Dmitry Sokolov

According to our database, Dmitry Sokolov authored at least 30 papers between 2011 and 2023.

Collaborative distances:

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

2023

Top-Down Lower Bounds for Depth-Four Circuits.

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

Electron. Colloquium Comput. Complex., 2023

Hardness Condensation by Restriction.

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

Electron. Colloquium Comput. Complex., 2023

Sampling and Certifying Symmetric Functions.

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2023

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

Dmitry Sokolov

Electron. Colloquium Comput. Complex., 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

2021

Lower Bounds on OBDD Proofs with Several Orders.

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

ACM Trans. Comput. Log., 2021

Pseudorandom Generators, Resolution and Heavy Width.

Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2021

Branching Programs with Bounded Repetitions and Flow Formulas.

Anastasia Sofronova, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 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

Monotone Circuit Lower Bounds from Resolution.

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

Theory Comput., 2020

On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables.

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

J. Symb. Log., 2020

(Semi)Algebraic Proofs over ±1 Variables.

Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2020

Automating Algebraic Proof Systems is NP-Hard.

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

Electron. Colloquium Comput. Complex., 2020

Resolution over linear equations modulo two.

Dmitry Itsykson, Dmitry Sokolov

Ann. Pure Appl. Log., 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

2019

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

Electron. Colloquium Comput. Complex., 2019

2018

Adventures in Monotone Complexity and TFNP.

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

Electron. Colloquium Comput. Complex., 2018

Reordering Rule Makes OBDD Proof Systems Stronger.

Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2018

2016

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

Dmitry Itsykson, Vsevolod Oparin, Mikhail Slabodkin, Dmitry Sokolov

Fundam. Informaticae, 2016

Dag-like Communication and Its Applications.

Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2016

2015

On the probabilistic closure of the loose unambiguous hierarchy.

Edward A. Hirsch, Dmitry Sokolov

Inf. Process. Lett., 2015

Complexity of distributions and average-case hardness.

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 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

Heuristic time hierarchies via hierarchies for sampling distributions.

Dmitry Itsykson, Alexander Knop, 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

2012

Lower bounds for myopic DPLL algorithms with a cut heuristic.

Dmitry Itsykson, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2012

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