Lower Bounds

In this page, we survey some of the lower bounds in algebraic complexity theory.

Open Problems

TODO: check full connection from RY'09 lower bounds to general circuit lower bounds - what improvement would be needed?

QUESTION: can multiplicative rank methods be used to prove lower bounds for general circuits? Can we get barriers for this?