Name
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 proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben-Sasson '09]}, and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [Razborov '16]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordstrom '08]. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.4230/LIPIcs.ICALP.2016.57 | international colloquium on automata languages and programming |
DocType | Volume | Issue |
Journal | abs/1612.07162 | 55 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Berkholz | 1 | 49 | 7.03 |
| Jakob Nordström | 2 | 177 | 21.76 |