Loading jsMath...
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: 927
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: 581
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