Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR20-001 | 8th January 2020 14:28

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

RSS-Feed




Revision #2
Authors: Susanna F. de Rezende, Or Meir, Jakob Nordström, Robert Robere
Accepted on: 8th January 2020 14:29
Downloads: 674
Keywords: 


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.


Revision #1 to TR20-001 | 7th January 2020 15:08

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling





Revision #1
Authors: Or Meir, Jakob Nordström, Robert Robere, Susanna F. de Rezende
Accepted on: 7th January 2020 15:08
Downloads: 439
Keywords: 


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.



Changes to previous version:

Updated affiliations, and added citation to TR19-186.


Paper:

TR20-001 | 31st December 2019 18:47

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling


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.



ISSN 1433-8092 | Imprint