Dmitry Sokolov

Orcid: 0000-0003-2809-3467

Affiliations:
  • EFPL, Switzerland
  • St. Petersburg State University, Russia
  • Russian Academy of Sciences, Steklov Institute of Mathematics, St. Petersburg, Russia
  • KTH Stockholm, Sweden (former)


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Top-Down Lower Bounds for Depth-Four Circuits.
Electron. Colloquium Comput. Complex., 2023

Hardness Condensation by Restriction.
Electron. Colloquium Comput. Complex., 2023

Sampling and Certifying Symmetric Functions.
Electron. Colloquium Comput. Complex., 2023

Random (log n)-CNF are Hard for Cutting Planes (Again).
Electron. Colloquium Comput. Complex., 2023

2022
A Lower Bound for <i>k</i>-DNF Resolution on Random CNF Formulas via Expansion.
Electron. Colloquium Comput. Complex., 2022

2021
Pseudorandom Generators, Resolution and Heavy Width.
Electron. Colloquium Comput. Complex., 2021

Branching Programs with Bounded Repetitions and Flow Formulas.
Electron. Colloquium Comput. Complex., 2021

The Power of Negative Reasoning.
Proceedings of the 36th Computational Complexity Conference, 2021

2020
On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables.
J. Symb. Log., 2020

(Semi)Algebraic Proofs over ±1 Variables.
Electron. Colloquium Comput. Complex., 2020

Automating Algebraic Proof Systems is NP-Hard.
Electron. Colloquium Comput. Complex., 2020

Lower Bounds on OBDD Proofs with Several Orders.
Electron. Colloquium Comput. Complex., 2020

Resolution over linear equations modulo two.
Ann. Pure Appl. Log., 2020

Trade-Offs Between Size and Degree in Polynomial Calculus.
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.
Electron. Colloquium Comput. Complex., 2019

2018
Adventures in Monotone Complexity and TFNP.
Electron. Colloquium Comput. Complex., 2018

Reordering Rule Makes OBDD Proof Systems Stronger.
Electron. Colloquium Comput. Complex., 2018

2017
Monotone Circuit Lower Bounds from Resolution.
Electron. Colloquium Comput. Complex., 2017

2016
Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles.
Fundam. Informaticae, 2016

Dag-like Communication and Its Applications.
Electron. Colloquium Comput. Complex., 2016

2015
On the probabilistic closure of the loose unambiguous hierarchy.
Inf. Process. Lett., 2015

Complexity of distributions and average-case hardness.
Electron. Colloquium Comput. Complex., 2015

Resolution Complexity of Perfect Matching Principles for Sparse Graphs.
Proceedings of the Computer Science - Theory and Applications, 2015

2014
On Fast Heuristic Non-deterministic Algorithms and Short Heuristic Proofs.
Fundam. Informaticae, 2014

Resolution complexity of perfect mathcing principles for sparse graphs.
Electron. Colloquium Comput. Complex., 2014

Heuristic time hierarchies via hierarchies for sampling distributions.
Electron. Colloquium Comput. Complex., 2014

Tree-like resolution complexity of two planar problems.
CoRR, 2014

Lower Bounds for Splittings by Linear Combinations.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2012
Lower bounds for myopic DPLL algorithms with a cut heuristic.
Electron. Colloquium Comput. Complex., 2012

2011
The Complexity of Inversion of Explicit Goldreich's Function by DPLL Algorithms.
Proceedings of the Computer Science - Theory and Applications, 2011


  Loading...