Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

01/08/2020
by   Susanna F. de Rezende, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset