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)...

Full description

Saved in:
Bibliographic Details
Published in:Foundations of computational mathematics 2016-06, Vol.16 (3), p.599-635
Main Authors: Gesmundo, Fulvio, Hauenstein, Jonathan D., Ikenmeyer, Christian, Landsberg, J. M.
Format: Article
Language:English
Subjects:
Algebra
Applications of Mathematics
Borders
Complexity
Computation
Computer Science
Economics
Foundations
Geometry, Algebraic
Linear and Multilinear Algebras
Math Applications in Computer Science
Mathematical analysis
Mathematical models
Mathematical research
Mathematics
Mathematics and Statistics
Matrices
Matrix Theory
Numerical Analysis
Rigidity
Vector spaces
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1615-3375
1615-3383
DOI:10.1007/s10208-015-9258-8