Abstract: We use algebraic geometry to study matrix rigidity, and more generally, the complexity
of computing a matrix-vector product. In particular, we (i) exhibit many
non-obvious equations testing for (border) rigidity, (ii) compute degrees of
varieties associated to rigidity, (iii) describe algebraic varieties associated to families
of matrices that are expected to have super-linear rigidity, and (iv) prove results about the ideals
and degrees of cones that are of interest in their own right.
