Loading...
Please wait, while we are loading the content...
Similar Documents
New lower bounds for the rank of matrix multiplication
| Content Provider | arXiv |
|---|---|
| Author | Landsberg, J. M. |
| Date of Submission | 2013-10-29 |
| Abstract | The rank of the matrix multiplication operator for nxn matrices is one of the most studied quantities in algebraic complexity theory. I prove that the rank is at least n^2-o(n^2). More precisely, for any integer p\leq n -1, the rank is at least (3- 1/(p+1))n^2-(1+2p\binom{2p}{p-1})n. The previous lower bound, due to Blaser, was 5n^2/2-3n (the case p=1). The new bounds improve Blaser's bound for all n>84. I also prove lower bounds for rectangular matrices significantly better than the the previous bound. |
| Related Links | https://arxiv.org/pdf/1206.1530.pdf |
| arXiv | 1206.1530 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Computational Complexity Mathematics - Algebraic Geometry Mathematics - Representation Theory Computer Science Mathematics |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
