×

Found 6 Documents (Results 1–6)

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
Full Text: DOI arXiv

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

Filter Results by …

Document Type

Year of Publication

Main Field