Fall 2018

Lifting Nullstellensatz Degree to Monotone Span Program Size

Tuesday, Sep. 11, 2018 10:00 am11:00 am

Add to Calendar


Robert Robere (University of Toronto)

In 1993, Karchmer and Wigderson introduced span programs, which are elegant computational devices that capture the complexity of computing with linear algebra over a field. We discuss some recent work characterizing the monotone span program size of certain "structured" boolean functions in terms of the Nullstellensatz degree required to refute a related unsatisfiable system of polynomial equations. This characterization leads to the resolution of a number of open problems on the complexity of span programs and unifies the proofs of many classic lower bounds in monotone complexity theory by appealing to known Nullstellensatz degree lower bounds.

This work is joint with Toniann Pitassi.