Standard
Supercritical space-width trade-offs for resolution. / Berkholz, Christoph; Nordström, Jakob.
43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. ed. / Yuval Rabani; Ioannis Chatzigiannakis; Davide Sangiorgi; Michael Mitzenmacher. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. 57 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 55).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Berkholz, C
& Nordström, J 2016,
Supercritical space-width trade-offs for resolution. in Y Rabani, I Chatzigiannakis, D Sangiorgi & M Mitzenmacher (eds),
43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016., 57, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 55, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy,
12/07/2016.
https://doi.org/10.4230/LIPIcs.ICALP.2016.57APA
Berkholz, C.
, & Nordström, J. (2016).
Supercritical space-width trade-offs for resolution. In Y. Rabani, I. Chatzigiannakis, D. Sangiorgi, & M. Mitzenmacher (Eds.),
43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 [57] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 55
https://doi.org/10.4230/LIPIcs.ICALP.2016.57Vancouver
Berkholz C
, Nordström J.
Supercritical space-width trade-offs for resolution. In Rabani Y, Chatzigiannakis I, Sangiorgi D, Mitzenmacher M, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2016. 57. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 55).
https://doi.org/10.4230/LIPIcs.ICALP.2016.57Author
Berkholz, Christoph ; Nordström, Jakob. / Supercritical space-width trade-offs for resolution. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. editor / Yuval Rabani ; Ioannis Chatzigiannakis ; Davide Sangiorgi ; Michael Mitzenmacher. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 55).
Bibtex
@inproceedings{941c5ea7a6d247f688460ae5506faafc,
title = "Supercritical space-width trade-offs for resolution",
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{\"o}m 2008].",
keywords = "Proof complexity, Resolution, Space, Supercritical, Trade-offs, Width",
author = "Christoph Berkholz and Jakob Nordstr{\"o}m",
year = "2016",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.ICALP.2016.57",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Yuval Rabani and Ioannis Chatzigiannakis and Davide Sangiorgi and Michael Mitzenmacher",
booktitle = "43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016",
note = "43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 ; Conference date: 12-07-2016 Through 15-07-2016",
}
RIS
TY - GEN
T1 - Supercritical space-width trade-offs for resolution
AU - Berkholz, Christoph
AU - Nordström, Jakob
PY - 2016/8/1
Y1 - 2016/8/1
N2 - 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].
AB - 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].
KW - Proof complexity
KW - Resolution
KW - Space
KW - Supercritical
KW - Trade-offs
KW - Width
UR - http://www.scopus.com/inward/record.url?scp=85012892631&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2016.57
DO - 10.4230/LIPIcs.ICALP.2016.57
M3 - Article in proceedings
AN - SCOPUS:85012892631
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
A2 - Rabani, Yuval
A2 - Chatzigiannakis, Ioannis
A2 - Sangiorgi, Davide
A2 - Mitzenmacher, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
Y2 - 12 July 2016 through 15 July 2016
ER -
