Följ
Dmitry Sokolov
Dmitry Sokolov
Verifierad e-postadress på epfl.ch
Titel
Citeras av
Citeras av
År
Monotone circuit lower bounds from resolution
A Garg, M Göös, P Kamath, D Sokolov
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018
622018
Adventures in monotone complexity and TFNP
M Göös, P Kamath, R Robere, D Sokolov
10th Innovations in Theoretical Computer Science Conference (ITCS 2019), 2019
442019
Dag-like communication and its applications
D Sokolov
International Computer Science Symposium in Russia, 294-307, 2017
362017
On obdd-based algorithms and proof systems that dynamically change the order of variables
D Itsykson, A Knop, A Romashchenko, D Sokolov
The Journal of Symbolic Logic 85 (2), 632-670, 2020
262020
Lower bounds for splittings by linear combinations
D Itsykson, D Sokolov
International Symposium on Mathematical Foundations of Computer Science, 372-383, 2014
262014
Reordering rule makes OBDD proof systems stronger
S Buss, D Itsykson, A Knop, D Sokolov
33rd Computational Complexity Conference (CCC 2018), 2018
222018
Resolution over linear equations modulo two
D Itsykson, D Sokolov
Annals of Pure and Applied Logic 171 (1), 102722, 2020
182020
Automating algebraic proof systems is NP-hard
SF De Rezende, M Göös, J Nordström, T Pitassi, R Robere, D Sokolov
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021
162021
The power of negative reasoning
SF de Rezende, M Lauria, J Nordström, D Sokolov
36th Computational Complexity Conference (CCC 2021), 2021
122021
(Semi) Algebraic proofs over {±1} variables
D Sokolov
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing …, 2020
112020
Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
SF de Rezende, J Nordström, K Risse, D Sokolov
arXiv preprint arXiv:1912.00534, 2019
82019
Lower bounds for myopic DPLL algorithms with a cut heuristic
D Itsykson, D Sokolov
Algorithms and Computation: 22nd International Symposium, ISAAC 2011 …, 2011
82011
Tight lower bounds on the resolution complexity of perfect matching principles
D Itsykson, V Oparin, M Slabodkin, D Sokolov
Fundamenta Informaticae 145 (3), 229-242, 2016
72016
Automating algebraic proof systems is np-hard
M Göös, J Nordström, T Pitassi, R Robere, SF de Rezende, D Sokolov
Electronic colloquium on computational complexity 27 (64), 2020
52020
Trade-offs between size and degree in polynomial calculus
G Lagarde, J Nordström, D Sokolov, J Swernofsky
11th Innovations in Theoretical Computer Science Conference (ITCS 2020), 2020
52020
The complexity of inverting explicit Goldreich’s function by DPLL algorithms
DM Itsykson, DO Sokolov
Journal of Mathematical Sciences 188, 47-58, 2013
52013
Sampling and certifying symmetric functions
Y Filmus, I Leigh, A Riazanov, D Sokolov
arXiv preprint arXiv:2305.04363, 2023
42023
Lower bounds on OBDD proofs with several orders
S Buss, D Itsykson, A Knop, A Riazanov, D Sokolov
ACM Transactions on Computational Logic (TOCL) 22 (4), 1-30, 2021
42021
The complexity of inversion of explicit Goldreich’s function by DPLL algorithms
D Itsykson, D Sokolov
Computer Science–Theory and Applications: 6th International Computer Science …, 2011
42011
The complexity of inversion of explicit Goldreich's function by DPLL algorithms
DM Itsykson, DO Sokolov
Записки научных семинаров ПОМИ 399 (0), 88-108, 2012
32012
Systemet kan inte utföra åtgärden just nu. Försök igen senare.
Artiklar 1–20