Supercritical space-width trade-offs for resolution
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfæ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].
Originalsprog | Engelsk |
---|---|
Titel | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 |
Redaktører | Yuval Rabani, Ioannis Chatzigiannakis, Davide Sangiorgi, Michael Mitzenmacher |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 1 aug. 2016 |
Artikelnummer | 57 |
ISBN (Elektronisk) | 9783959770132 |
DOI | |
Status | Udgivet - 1 aug. 2016 |
Eksternt udgivet | Ja |
Begivenhed | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 - Rome, Italien Varighed: 12 jul. 2016 → 15 jul. 2016 |
Konference
Konference | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 |
---|---|
Land | Italien |
By | Rome |
Periode | 12/07/2016 → 15/07/2016 |
Sponsor | AICA, Austrian, Facebook, Microsoft, Microsoft Research, Sapienza University of Rome, Department of Informatics |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 55 |
ISSN | 1868-8969 |
ID: 251868331