Past Events

Seminar

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

 

Download as iCal file

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

Committee

Rutgers/DIMACS Theory of Computing Seminar

Event Type: Seminar

Organization

IAS/DIMACS