Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Susanna F. de Rezende, Jakob Nordström, Or Meir, Robert Robere · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2019
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.