Complexity of Linear Circuits and Geometry Academic Article uri icon

abstract

  • © 2015, SFoCM. We use algebraic geometry to study matrix rigidity and, more generally, the complexity of computing a matrix–vector 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.

author list (cited authors)

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

citation count

  • 2

publication date

  • April 2015