Supercritical space-width trade-offs for resolution

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

Abstract

We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width resolution proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben- Sasson 2009], and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [Razborov 2016]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordström 2008].

Detaljer

Författare
Externa organisationer
  • Humboldt University of Berlin
  • KTH Royal Institute of Technology
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Titel på värdpublikation43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
RedaktörerYuval Rabani, Ioannis Chatzigiannakis, Davide Sangiorgi, Michael Mitzenmacher
FörlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elektroniskt)9783959770132
StatusPublished - 2016 aug 1
PublikationskategoriForskning
Peer review utfördJa
Externt publiceradJa
Evenemang43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 - Rome, Italien
Varaktighet: 2016 jul 122016 jul 15

Publikationsserier

NamnLeibniz International Proceedings in Informatics, LIPIcs
FörlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volym55
ISSN (tryckt)1868-8969

Konferens

Konferens43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
LandItalien
OrtRome
Period2016/07/122016/07/15