Supercritical space-width trade-offs for resolution

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

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].

OriginalsprogEngelsk
Titel43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
RedaktørerYuval Rabani, Ioannis Chatzigiannakis, Davide Sangiorgi, Michael Mitzenmacher
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato1 aug. 2016
Artikelnummer57
ISBN (Elektronisk)9783959770132
DOI
StatusUdgivet - 1 aug. 2016
Eksternt udgivetJa
Begivenhed43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 - Rome, Italien
Varighed: 12 jul. 201615 jul. 2016

Konference

Konference43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
LandItalien
ByRome
Periode12/07/201615/07/2016
SponsorAICA, Austrian, Facebook, Microsoft, Microsoft Research, Sapienza University of Rome, Department of Informatics
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind55
ISSN1868-8969

ID: 251868331