Asymptotic Rank Speedup Theorems, Revisited
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911703467294720 |
|---|---|
| author | Alman, Josh Li, Baitian |
| author_facet | Alman, Josh Li, Baitian |
| contents | Motivated by fast matrix multiplication and recent connections between asymptotic tensor rank and fine-grained complexity, we revisit classical tools from the matrix multiplication literature and develop a framework for obtaining improved asymptotic rank upper bounds for tensors beyond matrix multiplication.
In the 1980s, Coppersmith-Winograd and Strassen discovered a series of speedup theorems for asymptotic rank: in certain regimes, one can extract additional terms from a border rank upper bound on a tensor $T$, and then use these terms to obtain an improved asymptotic rank of $T$. We establish general speedup theorems that subsume these results and enable quantitative improvements. Two representative applications are:
(1) The asymptotic rank of the small Coppersmith-Winograd tensor $\mathrm{cw}_q$ is less than its border rank. For instance, we prove the asymptotic rank of $\mathrm{cw}_2$ is smaller than $3.931$, improving on $\underline{\mathrm{R}}(\mathrm{cw}_2)=4$. It is known that if the asymptotic rank of $\mathrm{cw}_2$ equals $3$, this would imply $ω=2$.
(2) A general improvement over Strassen's bound: we obtain an upper bound below $d^{2ω/3}$ on the asymptotic rank of any $d\times d\times d$ tensor.
To make full use of speedups, we analyze degenerations in which both sides are nontrivial direct sums, a setting where the optimal quantitative bound one can achieve was previously unclear. We do so via an approach we call Strassen calculus: a systematic method for converting such degeneration data into explicit asymptotic rank bounds using Strassen's theory of the asymptotic spectrum. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_21738 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Asymptotic Rank Speedup Theorems, Revisited Alman, Josh Li, Baitian Computational Complexity Data Structures and Algorithms Motivated by fast matrix multiplication and recent connections between asymptotic tensor rank and fine-grained complexity, we revisit classical tools from the matrix multiplication literature and develop a framework for obtaining improved asymptotic rank upper bounds for tensors beyond matrix multiplication. In the 1980s, Coppersmith-Winograd and Strassen discovered a series of speedup theorems for asymptotic rank: in certain regimes, one can extract additional terms from a border rank upper bound on a tensor $T$, and then use these terms to obtain an improved asymptotic rank of $T$. We establish general speedup theorems that subsume these results and enable quantitative improvements. Two representative applications are: (1) The asymptotic rank of the small Coppersmith-Winograd tensor $\mathrm{cw}_q$ is less than its border rank. For instance, we prove the asymptotic rank of $\mathrm{cw}_2$ is smaller than $3.931$, improving on $\underline{\mathrm{R}}(\mathrm{cw}_2)=4$. It is known that if the asymptotic rank of $\mathrm{cw}_2$ equals $3$, this would imply $ω=2$. (2) A general improvement over Strassen's bound: we obtain an upper bound below $d^{2ω/3}$ on the asymptotic rank of any $d\times d\times d$ tensor. To make full use of speedups, we analyze degenerations in which both sides are nontrivial direct sums, a setting where the optimal quantitative bound one can achieve was previously unclear. We do so via an approach we call Strassen calculus: a systematic method for converting such degeneration data into explicit asymptotic rank bounds using Strassen's theory of the asymptotic spectrum. |
| title | Asymptotic Rank Speedup Theorems, Revisited |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.21738 |