Skip to content Skip to navigation

Seminar: Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

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.

Speaker: 
Rob Robere
Location: 
CoRE 431
Event Date: 
10/16/2019 - 11:00am
Committee: 
Rutgers/DIMACS Theory of Computing Seminar
Event Type: 
Seminar
Organization: 
IAS/DIMACS