We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing 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 size $t+1$ ... more >>>

We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open ... more >>>

In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing.
This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing ... more >>>