Name
Abstract | ||
|---|---|---|
We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatz refutation of the pebbling formula over G in size t + 1 and degree s (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.4230/LIPIcs.CCC.2019.18 | Leibniz International Proceedings in Informatics |
Keywords | Field | DocType |
proof complexity,Nullstellensatz,pebble games,trade-offs,size,degree | Discrete mathematics,Graph,Computer science,Trade offs,If and only if | Conference |
Volume | ISSN | Citations |
137 | 1868-8969 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Susanna F. de Rezende | 1 | 13 | 4.35 |
| Jakob Nordström | 2 | 177 | 21.76 |
| Or Meir | 3 | 66 | 10.47 |
| Robert Robere | 4 | 0 | 2.03 |