ECCC-Report TR20-001https://eccc.weizmann.ac.il/report/2020/001Comments and Revisions published for TR20-001en-usWed, 08 Jan 2020 14:29:00 +0200
Revision 2
| Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling |
Susanna F. de Rezende,
Or Meir,
Jakob Nordström,
Robert Robere
https://eccc.weizmann.ac.il/report/2020/001#revision2We 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.Wed, 08 Jan 2020 14:29:00 +0200https://eccc.weizmann.ac.il/report/2020/001#revision2
Revision 1
| Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling |
Or Meir,
Susanna F. de Rezende,
Jakob Nordström,
Robert Robere
https://eccc.weizmann.ac.il/report/2020/001#revision1We 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.Tue, 07 Jan 2020 15:08:57 +0200https://eccc.weizmann.ac.il/report/2020/001#revision1
Paper TR20-001
| Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling |
Or Meir,
Susanna de Rezende,
Jakob Nordström,
Robert Robere
https://eccc.weizmann.ac.il/report/2020/001We 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.Wed, 01 Jan 2020 09:53:22 +0200https://eccc.weizmann.ac.il/report/2020/001