Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Wednesday, October 16, 2019, 11:00am
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
Rutgers/DIMACS Theory of Computing Seminar
Event Type: Seminar