Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)
Dmitry Sokolov
Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)
Dmitry Sokolov
Research interests:
Proof complexity, communication complexity, structural complexity, algorithms.
Papers, talks and posters
Papers
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Breaking Through the Reordering Obstacle in OBDD Proof Systems,
In progress
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