Circuit complexity, proof complexity, and polynomial identity testing

Joshua A. Grochow, Toniann Pitassi

We introduce a new algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolea…