Robert Robere “Nullstellensatz Size-Degree Trade-offs from the Reversible Pebbling Game” | Big Seminar

October 22, 2020
19.00 MSK (UTC +3)

Robert Robere "Nullstellensatz Size-Degree Trade-offs from the Reversible Pebbling Game"

Robert Robere from McGill University will give the talk "Nullstellensatz Size-Degree Trade-offs from the Reversible Pebbling Game" on the labs' Big Seminar.

The talk will be held in zoom
Meeting ID: 279-059-822
Password: first 6 decimal places of $\pi$ after the decimal point

You can also write to Alexander Polyanskii ( or to Maksim Zhukovskii ( if you want to be added to mailing list.


We discuss recent work in which we establish a tight relationship between Nullstellensatz certificates 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", a well-studied combinatorial 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 certificate of the pebbling formula over G in length t+1 and degree s. This result is independent of the underlying field of the Nullstellensatz certificate, and implies sharp bounds for other proof systems in the literature; furthermore, we can apply known reversible pebbling time-space tradeoffs to obtain strong length-degree trade-offs for Nullstellensatz certificates. To our knowledge these are the first strong tradeoffs known for this propositional proof system.

This is joint work with Susanna de Rezende, Or Meir and Jakob Nordstrom.

Watch the video:

Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.