default search action
Dmitry Sokolov 0001
Person information
- affiliation: EFPL, Switzerland
- affiliation: St. Petersburg State University, Russia
- affiliation: Russian Academy of Sciences, Steklov Institute of Mathematics, St. Petersburg, Russia
- affiliation (former): KTH Stockholm, Sweden
Other persons with the same name
- Dmitry Sokolov 0002 — University of Lorraine, LORIA, Nancy, France
- Dmitry Sokolov 0003 — Bauman Moscow State Technical University, Russia
- Dmitry Sokolov 0004 (aka: Dmitry V. Sokolov) — Siberian Branch of the Russian Academy of Sciences, Melentiev Energy Systems Institute, Irkutsk, Russia
- Dmitry Sokolov 0005 — St. Petersburg State University, Graduate School of Management, Russia
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c22]Dmitry Sokolov:
Random (log n)-CNF Are Hard for Cutting Planes (Again). STOC 2024: 2008-2015 - [c21]Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov:
Hardness Condensation by Restriction. STOC 2024: 2016-2027 - [i26]Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov:
Supercritical Tradeoffs for Monotone Circuits. Electron. Colloquium Comput. Complex. TR24: TR24-186 (2024) - 2023
- [c20]Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov:
Sampling and Certifying Symmetric Functions. APPROX/RANDOM 2023: 36:1-36:21 - [c19]Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov:
Top-Down Lower Bounds for Depth-Four Circuits. FOCS 2023: 1048-1055 - [i25]Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov:
Top-Down Lower Bounds for Depth-Four Circuits. CoRR abs/2304.02555 (2023) - [i24]Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov:
Sampling and Certifying Symmetric Functions. CoRR abs/2305.04363 (2023) - [i23]Dmitry Sokolov:
Random (log n)-CNF are Hard for Cutting Planes (Again). Electron. Colloquium Comput. Complex. TR23 (2023) - [i22]Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov:
Sampling and Certifying Symmetric Functions. Electron. Colloquium Comput. Complex. TR23 (2023) - [i21]Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov:
Hardness Condensation by Restriction. Electron. Colloquium Comput. Complex. TR23 (2023) - [i20]Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov:
Top-Down Lower Bounds for Depth-Four Circuits. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [c18]Dmitry Sokolov:
Pseudorandom Generators, Resolution and Heavy Width. CCC 2022: 15:1-15:22 - [i19]Anastasia Sofronova, Dmitry Sokolov:
A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j7]Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov:
Lower Bounds on OBDD Proofs with Several Orders. ACM Trans. Comput. Log. 22(4): 26:1-26:30 (2021) - [c17]Anastasia Sofronova, Dmitry Sokolov:
Branching Programs with Bounded Repetitions and Flow Formulas. CCC 2021: 17:1-17:25 - [c16]Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Dmitry Sokolov:
The Power of Negative Reasoning. CCC 2021: 40:1-40:24 - [c15]Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov:
Automating algebraic proof systems is NP-hard. STOC 2021: 209-222 - [i18]Anastasia Sofronova, Dmitry Sokolov:
Branching Programs with Bounded Repetitions and Flow Formulas. Electron. Colloquium Comput. Complex. TR21 (2021) - [i17]Dmitry Sokolov:
Pseudorandom Generators, Resolution and Heavy Width. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j6]Dmitry Itsykson, Dmitry Sokolov:
Resolution over linear equations modulo two. Ann. Pure Appl. Log. 171(1) (2020) - [j5]Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov:
On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables. J. Symb. Log. 85(2): 632-670 (2020) - [j4]Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov:
Monotone Circuit Lower Bounds from Resolution. Theory Comput. 16: 1-30 (2020) - [c14]Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov:
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. CCC 2020: 28:1-28:24 - [c13]Guillaume Lagarde, Jakob Nordström, Dmitry Sokolov, Joseph Swernofsky:
Trade-Offs Between Size and Degree in Polynomial Calculus. ITCS 2020: 72:1-72:16 - [c12]Dmitry Sokolov:
(Semi)Algebraic proofs over ±1 variables. STOC 2020: 78-90 - [i16]Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov:
Lower Bounds on OBDD Proofs with Several Orders. Electron. Colloquium Comput. Complex. TR20 (2020) - [i15]Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna F. de Rezende:
Automating Algebraic Proof Systems is NP-Hard. Electron. Colloquium Comput. Complex. TR20 (2020) - [i14]Dmitry Sokolov:
(Semi)Algebraic Proofs over ±1 Variables. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [c11]Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov:
Adventures in Monotone Complexity and TFNP. ITCS 2019: 38:1-38:19 - [i13]Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov:
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. CoRR abs/1912.00534 (2019) - [i12]Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov:
On OBDD-based algorithms and proof systems that dynamically change order of variables. Electron. Colloquium Comput. Complex. TR19 (2019) - [i11]Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov:
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [c10]Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov:
Reordering Rule Makes OBDD Proof Systems Stronger. CCC 2018: 16:1-16:24 - [c9]Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov:
Monotone circuit lower bounds from resolution. STOC 2018: 902-911 - [i10]Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov:
Reordering Rule Makes OBDD Proof Systems Stronger. Electron. Colloquium Comput. Complex. TR18 (2018) - [i9]Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov:
Adventures in Monotone Complexity and TFNP. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c8]Dmitry Sokolov:
Dag-Like Communication and Its Applications. CSR 2017: 294-307 - [c7]Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov:
On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables. STACS 2017: 43:1-43:14 - [i8]Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov:
Monotone Circuit Lower Bounds from Resolution. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j3]Dmitry Itsykson, Vsevolod Oparin, Mikhail Slabodkin, Dmitry Sokolov:
Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles. Fundam. Informaticae 145(3): 229-242 (2016) - [c6]Dmitry Itsykson, Alexander Knop, Dmitry Sokolov:
Complexity of Distributions and Average-Case Hardness. ISAAC 2016: 38:1-38:12 - [i7]Dmitry Sokolov:
Dag-like Communication and Its Applications. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j2]Edward A. Hirsch, Dmitry Sokolov:
On the probabilistic closure of the loose unambiguous hierarchy. Inf. Process. Lett. 115(9): 725-730 (2015) - [c5]Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov:
Resolution Complexity of Perfect Matching Principles for Sparse Graphs. CSR 2015: 219-230 - [c4]Dmitry Itsykson, Alexander Knop, Dmitry Sokolov:
Heuristic Time Hierarchies via Hierarchies for Sampling Distributions. ISAAC 2015: 201-211 - [i6]Dmitry Itsykson, Alexander Knop, Dmitry Sokolov:
Complexity of distributions and average-case hardness. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j1]Dmitry Itsykson, Dmitry Sokolov:
On Fast Heuristic Non-deterministic Algorithms and Short Heuristic Proofs. Fundam. Informaticae 132(1): 113-129 (2014) - [c3]Dmitry Itsykson, Dmitry Sokolov:
Lower Bounds for Splittings by Linear Combinations. MFCS (2) 2014: 372-383 - [i5]Dmitry Itsykson, Anna Malova, Vsevolod Oparin, Dmitry Sokolov:
Tree-like resolution complexity of two planar problems. CoRR abs/1412.1124 (2014) - [i4]Edward A. Hirsch, Dmitry Sokolov:
On the probabilistic closure of the loose unambiguous hierarchy. Electron. Colloquium Comput. Complex. TR14 (2014) - [i3]Dmitry Itsykson, Alexander Knop, Dmitry Sokolov:
Heuristic time hierarchies via hierarchies for sampling distributions. Electron. Colloquium Comput. Complex. TR14 (2014) - [i2]Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov:
Resolution complexity of perfect mathcing principles for sparse graphs. Electron. Colloquium Comput. Complex. TR14 (2014) - 2012
- [i1]Dmitry Itsykson, Dmitry Sokolov:
Lower bounds for myopic DPLL algorithms with a cut heuristic. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [c2]Dmitry Itsykson, Dmitry Sokolov:
The Complexity of Inversion of Explicit Goldreich's Function by DPLL Algorithms. CSR 2011: 134-147 - [c1]Dmitry Itsykson, Dmitry Sokolov:
Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic. ISAAC 2011: 464-473
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from , , and to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-11-25 22:45 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint