Complexity of Linear Circuits and Geometry Academic Article uri icon


  • 2015, SFoCM. We use algebraic geometry to study matrix rigidity and, more generally, the complexity of computing a matrixvector product, continuing a study initiated in Kumar et al. (2009), Landsberg et al. (preprint). In particular, we (1) exhibit many non-obvious equations testing for (border) rigidity, (2) compute degrees of varieties associated with rigidity, (3) describe algebraic varieties associated with families of matrices that are expected to have super-linear rigidity, and (4) prove results about the ideals and degrees of cones that are of interest in their own right.

published proceedings

  • Foundations of Computational Mathematics

author list (cited authors)

  • Gesmundo, F., Hauenstein, J. D., Ikenmeyer, C., & Landsberg, J. M.

citation count

  • 2

complete list of authors

  • Gesmundo, Fulvio||Hauenstein, Jonathan D||Ikenmeyer, Christian||Landsberg, JM

publication date

  • June 2016