Complexity of Linear Circuits and Geometry (pdf)

Fulvio Gesmundo, Jonathan Hauenstein, Christian Ikenmeyer, and JM Landsberg.

Abstract: We use algebraic geometry to study matrix rigidity, and more generally, the complexity of computing a matrix-vector product. In particular, we (i) exhibit many non-obvious equations testing for (border) rigidity, (ii) compute degrees of varieties associated to rigidity, (iii) describe algebraic varieties associated to families of matrices that are expected to have super-linear rigidity, and (iv) prove results about the ideals and degrees of cones that are of interest in their own right.

Computational Proofs:
Proposition 3.3.1
Proposition 3.3.2
Proposition 3.3.4
Proposition 4.5.2

Research supported by the National Science Foundation under DMS-1006353 and DMS-1262428, and DARPA Young Faculty Award.