Robert Robere, DIMACS

Abstract

We discuss recent work in which we establish a tight relationship between Nullstellensatz proofs of the so-called "pebbling" formulas --- which play an important role in a variety of results in proof complexity, circuit complexity, and logic --- and the reversible pebbling game on directed graphs. To be precise: we show 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 length t+1 and degree s. This result is independent of the underlying field of the Nullstellensatz refutation, and implies sharp bounds for other proof systems and other models in query complexity; furthermore, we can apply known reversible pebbling time-space tradeoffs to obtain strong length-degree trade-offs for Nullstellensatz proofs.

This is joint work with Jakob Nordstrom, Susanna F. de Rezende, and Or Meir.