| 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 | 74 | 2018 |
| Adventures in monotone complexity and TFNP M Göös, P Kamath, R Robere, D Sokolov 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), 38 …, 2019 | 51 | 2019 |
| Dag-like communication and its applications D Sokolov International Computer Science Symposium in Russia, 294-307, 2017 | 39 | 2017 |
| 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 | 28* | 2021 |
| 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 | 26 | 2020 |
| Resolution over linear equations modulo two D Itsykson, D Sokolov Annals of Pure and Applied Logic 171 (1), 102722, 2020 | 26 | 2020 |
| Lower bounds for splittings by linear combinations D Itsykson, D Sokolov International Symposium on Mathematical Foundations of Computer Science, 372-383, 2014 | 26 | 2014 |
| Reordering rule makes OBDD proof systems stronger S Buss, D Itsykson, A Knop, D Sokolov 33rd Computational Complexity Conference (CCC 2018), 16: 1-16: 24, 2018 | 21 | 2018 |
| (Semi) Algebraic proofs over {±1} variables D Sokolov Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing …, 2020 | 17 | 2020 |
| The power of negative reasoning SF de Rezende, M Lauria, J Nordström, D Sokolov 36th Computational Complexity Conference (CCC 2021), 40: 1-40: 24, 2021 | 15 | 2021 |
| The complexity of inverting explicit Goldreich’s function by DPLL algorithms DM Itsykson, DO Sokolov Journal of Mathematical Sciences 188, 47-58, 2013 | 12 | 2013 |
| Lower bounds for myopic DPLL algorithms with a cut heuristic D Itsykson, D Sokolov Algorithms and Computation: 22nd International Symposium, ISAAC 2011 …, 2011 | 9 | 2011 |
| 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 | 8 | 2016 |
| 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 | 7 | 2019 |
| Sampling and certifying symmetric functions Y Filmus, I Leigh, A Riazanov, D Sokolov arXiv preprint arXiv:2305.04363, 2023 | 5 | 2023 |
| 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 | 5 | 2021 |
| 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), 72 …, 2020 | 4 | 2020 |
| Supercritical tradeoffs for monotone circuits M Göös, G Maystre, K Risse, D Sokolov arXiv preprint arXiv:2411.14268, 2024 | 2 | 2024 |
| Hardness condensation by restriction M Göös, I Newman, A Riazanov, D Sokolov Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2016-2027, 2024 | 2 | 2024 |
| A Lower Bound for 𝑘-DNF Resolution on Random CNF Formulas via Expansion A Sofronova, D Sokolov | 2* | 2022 |
Dmitry ItsyksonSteklov Institute of Mathematics at St. PetersburgVerified email at pdmi.ras.ru
