Seminars & Colloquia Calendar
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Rob Robere (IAS/DIMACS)
Location: CoRE 301
Date & time: Wednesday, 16 October 2019 at 11:00AM - 12:00PM
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.