Complexity of Linear Circuits and Geometry
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
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.