Dmitry Sokolov
Research interests:
Proof complexity, communication complexity, structural complexity, algorithms.

Last updated: 09.06.2021
Papers, talks and posters
Papers
Dmitry Sokolov
"Pseudorandom Generators, Resolution and Heavy Width",
In progress
Susanna F. de Rezende, Susanna F. de Rezende, Jakob Nordström, Dmitry Sokolov
The Power of Negative Reasoning,
Appear in proceedings of CCC 2021
Anastasia Sofronova, Dmitry Sokolov
"Branching Programs with Bounded Repetitions and Flow Formulas",
Appear in proceedings of CCC 2021
Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov
"Automating Algebraic Proof Systems is NP-Hard",
Appear in proceedings of STOC 2021
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
"Lower Bounds on OBDD Proofs with Several Orders",
Appear in ACM Transactions on Computational Logic (TOCL)
Dmitry Sokolov
"(Semi)Algebraic Proofs over {-1, +1} Variables",
Appear in proceedings of STOC 2020
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
"Exponential Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs",
Appear in proceedings of CCC 2020
Guillaume Lagarde, Jakob Nordström, Dmitry Sokolov, Joseph Swernofsky
"Trade-offs Between Size and Degree in Polynomial Calculus",
Appear in proceedings of ITCS 2020
Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
"Adventures in Monotone Complexity and TFNP",
Appear in proceedings of ITCS 2019
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
"Reordering Rule Makes OBDD Proof Systems Stronger",
Appear in proceedings of CCC 2018
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
"Monotone Circuit Lower Bounds from Resolution",
Appear in proceedings of STOC 2018
Dmitry Sokolov
"Dag-like Communication and Its Applications",
Appear in proceedings of CSR 2017
Dmitry Itsykson, Alexander Knop, Andrey Romashchenko, Dmitry Sokolov
"On OBDD based algorithms and proof systems that dynamically change order of variables",
Appear in proceedings of STACS 2017
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
"Complexity of distributions and average-case hardness",
Appear in proceedings of ISAAC 2016
Dmitry Itsykson, Vsevolod Oparin, Mikhail Slabodkin, Dmitry Sokolov
"Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles",
Fundamenta Informaticae, vol. 145, no. 3, pp. 229-242, 2016
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
"Heuristic Time Hierarchies via Hierarchies for Sampling Distributions",
Appear in proceedings of ISAAC 2015, [Bib]
Edward A. Hirsch, Dmitry Sokolov
"On the probabilistic closure of the loose unambiguous hierarchy",
Information Processing Letters, Vol. 115(9), pp. 725-730, 2015, [Bib]
Dmitry Itsykson, Dmitry Sokolov
"Lower bounds for splittings by linear combinations",
In proceedings of MFCS 2014
Dmitry Itsykson, Dmitry Sokolov
"On fast non-deterministic algorithms and short heuristic proofs",
Fundamenta Informaticae, 132(1):113-129, 2014
Dmitry Itsykson, Anna Malova, Vsevolod Oparin, Dmitry Sokolov
"Tree-like resolution complexity of two planar problems",
CoRR abs/1412.1124, 2014
Dmitry Itsykson, Dmitry Sokolov
"Lower bounds for myopic DPLL algorithms with a cut heuristic",
In proceedings of ISAAC 2011
Dmitry Itsykson, Dmitry Sokolov
"The complexity of inversion of explicit Goldreich's function by DPLL algorithms",
Journal of Mathematical Sciences, 399:88-109, 2012
Talks
In progress