Complexity of Linear Circuits and Geometry

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.