Abstract
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.