Complexity of Linear Circuits and Geometry
- Additional Document Info
- View All
© 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.