Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

 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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.