De Rezende, Susanna F.; Nordström, Jakob; Risse, Kilian; Sokolov, Dmitry Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs. (English) Zbl 07561756 Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 28, 24 p. (2020). MSC: 68Q25 PDFBibTeX XMLCite \textit{S. F. De Rezende} et al., LIPIcs -- Leibniz Int. Proc. Inform. 169, Article 28, 24 p. (2020; Zbl 07561756) Full Text: DOI arXiv
Garg, Ankit; Göös, Mika; Kamath, Pritish; Sokolov, Dmitry Monotone circuit lower bounds from resolution. (English) Zbl 1462.68036 Theory Comput. 16, Paper No. 13, 30 p. (2020). MSC: 68Q06 03F20 68Q11 68Q17 PDFBibTeX XMLCite \textit{A. Garg} et al., Theory Comput. 16, Paper No. 13, 30 p. (2020; Zbl 1462.68036) Full Text: DOI
Itsykson, Dmitry; Sokolov, Dmitry Resolution over linear equations modulo two. (English) Zbl 07127339 Ann. Pure Appl. Logic 171, No. 1, Article ID 102722, 31 p. (2020). MSC: 03F20 68Q17 PDFBibTeX XMLCite \textit{D. Itsykson} and \textit{D. Sokolov}, Ann. Pure Appl. Logic 171, No. 1, Article ID 102722, 31 p. (2020; Zbl 07127339) Full Text: DOI
Göös, Mika; Kamath, Pritish; Robere, Robert; Sokolov, Dmitry Adventures in monotone complexity and TFNP. (English) Zbl 07559081 Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 38, 19 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{M. Göös} et al., LIPIcs -- Leibniz Int. Proc. Inform. 124, Article 38, 19 p. (2019; Zbl 07559081) Full Text: DOI
Buss, Sam; Itsykson, Dmitry; Knop, Alexander; Sokolov, Dmitry Reordering rule makes OBDD proof systems stronger. (English) Zbl 1441.03042 Servedio, Rocco A. (ed.), 33rd computational complexity conference, CCC 2018, June 22–24, 2018, San Diego, California, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 102, Article 16, 24 p. (2018). MSC: 03F20 68P05 PDFBibTeX XMLCite \textit{S. Buss} et al., LIPIcs -- Leibniz Int. Proc. Inform. 102, Article 16, 24 p. (2018; Zbl 1441.03042) Full Text: DOI
Itsykson, Dmitry; Sokolov, Dmitry The complexity of inversion of explicit Goldreich’s function by DPLL algorithms. (English) Zbl 1332.68058 Kulikov, Alexander (ed.) et al., Computer science – theory and applications. 6th international computer science symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14–18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20711-2/pbk). Lecture Notes in Computer Science 6651, 134-147 (2011). MSC: 68Q17 94A60 PDFBibTeX XMLCite \textit{D. Itsykson} and \textit{D. Sokolov}, Lect. Notes Comput. Sci. 6651, 134--147 (2011; Zbl 1332.68058) Full Text: DOI