Complexity of linear circuits and geometry
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › fagfællebedømt
We use algebraic geometry to study matrix rigidity, and more generally, the complexity of computing a matrix-vector product, continuing a study initiated by Kumar, et. al. 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.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Foundations of Computational Mathematics |
Vol/bind | 16 |
Udgave nummer | 3 |
Sider (fra-til) | 599–635 |
ISSN | 1615-3375 |
Status | Udgivet - 2016 |
Eksternt udgivet | Ja |
Links
- https://arxiv.org/abs/1310.1362
Accepteret manuskript
ID: 189700549