pith. sign in

arxiv: 2605.21738 · v1 · pith:ABVGBWTDnew · submitted 2026-05-20 · 💻 cs.CC · cs.DS

Asymptotic Rank Speedup Theorems, Revisited

Josh Alman , Baitian Li This is my paper

Pith reviewed 2026-05-22 07:25 UTC · model grok-4.3

classification 💻 cs.CC cs.DS
keywords asymptotic tensor rankCoppersmith-Winograd tensorspeedup theoremsmatrix multiplication exponentStrassen calculusborder ranktensor degenerationasymptotic spectrum
0
0 comments X

The pith

The asymptotic rank of the Coppersmith-Winograd tensor cw_2 is smaller than 3.931, below its border rank of 4.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops general speedup theorems that improve asymptotic rank upper bounds for tensors by extracting additional terms from border rank information in specific regimes. These theorems generalize classical results from Coppersmith-Winograd and Strassen and rely on a new method called Strassen calculus to handle degenerations of direct sums of nontrivial tensors. Applied to the small Coppersmith-Winograd tensor, the work shows that the asymptotic rank of cw_2 is less than 3.931. A sympathetic reader would care because reaching an asymptotic rank of exactly 3 for this tensor would imply that the matrix multiplication exponent ω equals 2. The results also give a general improvement, bounding the asymptotic rank of any d by d by d tensor below d to the power 2ω/3.

Core claim

The authors prove general asymptotic rank speedup theorems that subsume earlier work and enable quantitative improvements beyond previous bounds. For the Coppersmith-Winograd tensor cw_2 they establish an asymptotic rank upper bound smaller than 3.931, improving on the known border rank of 4. They also obtain an upper bound below d^{2ω/3} on the asymptotic rank of an arbitrary d by d by d tensor. The proofs rest on analyzing degenerations where both sides are nontrivial direct sums and converting the data into explicit bounds via Strassen calculus.

What carries the argument

Strassen calculus, a systematic method for converting degeneration data of direct sums of nontrivial tensors into explicit asymptotic rank bounds using Strassen's theory of the asymptotic spectrum.

If this is right

  • If the asymptotic rank of cw_2 equals 3, then the matrix multiplication exponent ω equals 2.
  • The asymptotic rank of any d by d by d tensor is bounded above by a quantity smaller than d to the power 2ω/3.
  • Border rank upper bounds on tensors can be converted into strictly better asymptotic rank upper bounds through the speedup theorems in appropriate regimes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The Strassen calculus approach could be applied to other families of tensors to derive improved rank bounds in fine-grained complexity.
  • Further refinements to the degeneration analysis might close the remaining gap between the new upper bound and the conjectured value of 3 for cw_2.
  • The framework may clarify relationships between border rank and asymptotic rank for tensors arising in other algebraic complexity problems.

Load-bearing premise

The quantitative improvements rest on the correctness of the degeneration analysis for direct sums of nontrivial tensors and the faithful conversion of that data into asymptotic rank bounds via Strassen calculus.

What would settle it

A new lower bound or exhaustive computation establishing that the asymptotic rank of cw_2 is at least 3.932 would contradict the claimed upper bound of smaller than 3.931.

read the original abstract

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 $\omega=2$. (2) A general improvement over Strassen's bound: we obtain an upper bound below $d^{2\omega/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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript develops general speedup theorems for asymptotic tensor rank that extend classical results of Coppersmith-Winograd and Strassen. These theorems apply to degenerations in which both source and target are nontrivial direct sums. The paper introduces Strassen calculus as a systematic method for converting such degeneration data into explicit upper bounds on asymptotic rank via Strassen's asymptotic spectrum. Two main applications are presented: an explicit improvement showing that the asymptotic rank of cw_2 is strictly less than 3.931 (improving on its border rank of 4), and a general upper bound strictly below d^{2ω/3} for the asymptotic rank of any d×d×d tensor.

Significance. If the central claims hold, the work supplies a reusable framework for quantitative asymptotic-rank improvements outside the matrix-multiplication setting and gives the first explicit numerical improvement for the asymptotic rank of cw_2. The general bound below d^{2ω/3} is a modest but uniform advance over Strassen's classical estimate. The treatment of nontrivial direct-sum degenerations addresses a technical gap that had limited the applicability of earlier speedup theorems.

major comments (1)
  1. [Strassen calculus and applications to cw_q] Section on Strassen calculus and applications to cw_q: the claimed bound R(cw_2) < 3.931 is obtained by feeding a specific direct-sum degeneration into the asymptotic-spectrum extraction. The manuscript should exhibit the intermediate numerical values (exponents, multiplicities, and spectrum coordinates) used in this extraction so that the arithmetic can be independently verified; an error in the handling of the additive structure would invalidate the numerical improvement while leaving the qualitative speedup theorem intact.
minor comments (2)
  1. [Strassen calculus] The notation for border rank and asymptotic rank is used consistently, but a short reminder of the precise definitions of underline{R}(T) and R(T) at the beginning of the Strassen-calculus section would help readers who are not specialists in tensor-rank theory.
  2. Figure 1 (or the corresponding diagram of the degeneration) would benefit from explicit labels on the source and target direct-summands to make the nontriviality of both sides immediately visible.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation and the recommendation of minor revision. The suggestion to make the numerical extraction for the cw_2 bound fully verifiable is constructive, and we address it directly below.

read point-by-point responses

  1. Referee: [Strassen calculus and applications to cw_q] Section on Strassen calculus and applications to cw_q: the claimed bound R(cw_2) < 3.931 is obtained by feeding a specific direct-sum degeneration into the asymptotic-spectrum extraction. The manuscript should exhibit the intermediate numerical values (exponents, multiplicities, and spectrum coordinates) used in this extraction so that the arithmetic can be independently verified; an error in the handling of the additive structure would invalidate the numerical improvement while leaving the qualitative speedup theorem intact.

    Authors: We agree that explicit display of the intermediate values improves verifiability. In the revised manuscript we will insert a dedicated paragraph (or short appendix) that lists the precise exponents, multiplicities, and asymptotic-spectrum coordinates obtained from the direct-sum degeneration of cw_2. This will make the arithmetic steps transparent and confirm the correct handling of the additive structure, thereby establishing R(cw_2) < 3.931 without altering any other claims. The underlying qualitative speedup theorem is unaffected by this presentational change. revision: yes

Circularity Check

0 steps flagged

No significant circularity; bounds derived from general theorems applied to external data

full rationale

The paper develops general speedup theorems that subsume classical results and applies them via Strassen calculus to known degeneration data for tensors such as cw_2. The improved asymptotic rank bound <3.931 is obtained by converting nontrivial direct-sum degeneration information into an explicit upper bound using Strassen's asymptotic spectrum, without any reduction of the output to a fitted parameter, self-defined quantity, or load-bearing self-citation chain. The central claims remain independent of the specific numerical inputs and rest on the correctness of the general framework rather than tautological equivalence.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on Strassen's existing theory of the asymptotic spectrum as background; no new free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Strassen's theory of the asymptotic spectrum
    Invoked to convert degeneration data into explicit asymptotic rank bounds.

pith-pipeline@v0.9.0 · 5835 in / 1178 out tokens · 32806 ms · 2026-05-22T07:25:58.511676+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

49 extracted references · 49 canonical work pages

  1. [1]

    2023 IEEE 64th annual symposium on Foundations of Computer Science (FOCS) , pages=

    Faster matrix multiplication via asymmetric hashing , author=. 2023 IEEE 64th annual symposium on Foundations of Computer Science (FOCS) , pages=. 2023 , organization=

    work page 2023

  2. [2]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    New bounds for matrix multiplication: from alpha to omega , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    work page 2024

  3. [3]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    More asymmetry yields faster matrix multiplication , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    work page 2025

  4. [4]

    and Ventura, Emanuele , TITLE =

    Conner, Austin and Gesmundo, Fulvio and Landsberg, Joseph M. and Ventura, Emanuele , TITLE =. Comput. Complexity , FJOURNAL =. 2022 , NUMBER =. doi:10.1007/s00037-021-00217-y , URL =

    work page doi:10.1007/s00037-021-00217-y 2022

  5. [5]

    and Winograd, S

    Coppersmith, D. and Winograd, S. , TITLE =. SIAM J. Comput. , FJOURNAL =. 1982 , NUMBER =. doi:10.1137/0211038 , URL =

    work page doi:10.1137/0211038 1982

  6. [6]

    , TITLE =

    Strassen, V. , TITLE =. J. Reine Angew. Math. , FJOURNAL =. 1988 , PAGES =. doi:10.1515/crll.1988.384.102 , URL =

    work page doi:10.1515/crll.1988.384.102 1988

  7. [7]

    2025 , month =

    Petteri Kaski , title =. 2025 , month =

    work page 2025

  8. [8]

    , TITLE =

    Strassen, V. , TITLE =. J. Reine Angew. Math. , FJOURNAL =. 1987 , PAGES =. doi:10.1515/crll.1987.375-376.406 , URL =

    work page doi:10.1515/crll.1987.375-376.406 1987

  9. [9]

    Schönhage

    Sch\"onhage, A. , TITLE =. SIAM J. Comput. , FJOURNAL =. 1981 , NUMBER =. doi:10.1137/0210032 , URL =

    work page doi:10.1137/0210032 1981

  10. [10]

    Avi Wigderson and Jeroen Zuiddam , title =. Bull. Amer. Math. Soc. , fjournal =. 2026 , volume =

    work page 2026

  11. [11]

    Combinatorica , FJOURNAL =

    Zuiddam, Jeroen , TITLE =. Combinatorica , FJOURNAL =. 2019 , NUMBER =. doi:10.1007/s00493-019-3992-5 , URL =

    work page doi:10.1007/s00493-019-3992-5 2019

  12. [12]

    Fast Matrix Multiplication , year =

    Bl. Fast Matrix Multiplication , year =. doi:10.4086/toc.gs.2013.005 , publisher =

    work page doi:10.4086/toc.gs.2013.005 2013

  13. [13]

    Romani, Francesco , TITLE =. SIAM J. Comput. , FJOURNAL =. 1982 , NUMBER =. doi:10.1137/0211020 , URL =

    work page doi:10.1137/0211020 1982

  14. [14]

    Pan, V. Ya. , TITLE =. Comput. Math. Appl. , FJOURNAL =. 1981 , NUMBER =. doi:10.1016/0898-1221(81)90009-2 , URL =

    work page doi:10.1016/0898-1221(81)90009-2 1981

  15. [15]

    IEEE Trans

    Haemers, Willem , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 1979 , NUMBER =. doi:10.1109/TIT.1979.1056027 , URL =

    work page doi:10.1109/tit.1979.1056027 1979

  16. [16]

    Combinatorica , FJOURNAL =

    Alon, Noga , TITLE =. Combinatorica , FJOURNAL =. 1998 , NUMBER =. doi:10.1007/PL00009824 , URL =

    work page doi:10.1007/pl00009824 1998

  17. [17]

    2025 IEEE Annual Symposium on Foundations of Computer Science (FOCS) , year=

    Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum , author=. 2025 IEEE Annual Symposium on Foundations of Computer Science (FOCS) , year=

    work page 2025

  18. [18]

    2013 , publisher=

    Algebraic complexity theory , author=. 2013 , publisher=

    work page 2013

  19. [19]

    2026 , eprint=

    Asymptotic rank bounds: a numerical census , author=. 2026 , eprint=

    work page 2026

  20. [20]

    16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , pages=

    A Universal Sequence of Tensors for the Asymptotic Rank Conjecture , author=. 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , pages=. 2025 , doi=

    work page 2025

  21. [21]

    Linear Algebra Appl

    Lickteig, Thomas , TITLE =. Linear Algebra Appl. , FJOURNAL =. 1985 , PAGES =. doi:10.1016/0024-3795(85)90070-9 , URL =

    work page doi:10.1016/0024-3795(85)90070-9 1985

  22. [22]

    , TITLE =

    Strassen, V. , TITLE =. Linear Algebra Appl. , FJOURNAL =. 1983 , PAGES =. doi:10.1016/0024-3795(83)80041-X , URL =

    work page doi:10.1016/0024-3795(83)80041-x 1983

  23. [23]

    Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

    Error-correction of matrix multiplication algorithms , author=. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=. 2025 , doi =

    work page 2025

  24. [24]

    52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages=

    An Optimal Error-Correcting Reduction for Matrix Multiplication , author=. 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages=. 2025 , doi=

    work page 2025

  25. [25]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

    A stronger connection between the asymptotic rank conjecture and the set cover conjecture , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=. 2024 , doi=

    work page 2024

  26. [26]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

    The asymptotic rank conjecture and the set cover conjecture are not both true , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=. 2024 , doi=

    work page 2024

  27. [27]

    Symmetric powers: structure, smoothability, and applications , JOURNAL =

    Flavi, Cosimo and Jelisiejew, Joachim and Micha. Symmetric powers: structure, smoothability, and applications , JOURNAL =. 2025 , NUMBER =. doi:10.1093/imrn/rnaf277 , URL =

    work page doi:10.1093/imrn/rnaf277 2025

  28. [28]

    , TITLE =

    Strassen, V. , TITLE =. J. Reine Angew. Math. , FJOURNAL =. 1991 , PAGES =. doi:10.1515/crll.1991.413.127 , URL =

    work page doi:10.1515/crll.1991.413.127 1991

  29. [29]

    Jahresber

    Strassen, Volker , TITLE =. Jahresber. Deutsch. Math.-Verein. , FJOURNAL =. 2005 , NUMBER =

    work page 2005

  30. [30]

    Christandl, Matthias and Vrana, P\'eter and Zuiddam, Jeroen , TITLE =. J. Amer. Math. Soc. , FJOURNAL =. 2023 , NUMBER =. doi:10.1090/jams/996 , URL =

    work page doi:10.1090/jams/996 2023

  31. [31]

    2026 , eprint=

    Strassen's support functionals coincide with the quantum functionals , author=. 2026 , eprint=

    work page 2026

  32. [32]

    Robert Robere and Jeroen Zuiddam , title =. 62nd. 2021 , url =

    work page 2021

  33. [33]

    Baker, Theodore and Gill, John and Solovay, Robert , TITLE =. SIAM J. Comput. , FJOURNAL =. 1975 , NUMBER =. doi:10.1137/0204037 , URL =

    work page doi:10.1137/0204037 1975

  34. [34]

    Coppersmith, Don and Winograd, Shmuel , TITLE =. J. Symbolic Comput. , FJOURNAL =. 1990 , NUMBER =. doi:10.1016/S0747-7171(08)80013-2 , URL =

    work page doi:10.1016/s0747-7171(08)80013-2 1990

  35. [35]

    Landsberg and Fulvio Gesmundo and Emanuele Ventura , title =

    Austin Conner and Joseph M. Landsberg and Fulvio Gesmundo and Emanuele Ventura , title =. 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , volume =. 2020 , doi =

    work page 2020

  36. [36]

    Christandl, Matthias and Lysikov, Vladimir and Zuiddam, Jeroen , TITLE =. J. Math. Pures Appl. (9) , FJOURNAL =. 2023 , PAGES =. doi:10.1016/j.matpur.2023.02.006 , URL =

    work page doi:10.1016/j.matpur.2023.02.006 2023

  37. [37]

    Theory Comput

    Christandl, Matthias and Vrana, P\'eter and Zuiddam, Jeroen , TITLE =. Theory Comput. , FJOURNAL =. 2021 , PAGES =. doi:10.4086/toc.2021.v017a002 , URL =

    work page doi:10.4086/toc.2021.v017a002 2021

  38. [38]

    Barriers for rectangular matrix multiplication , JOURNAL =

    Christandl, Matthias and Le Gall, Fran. Barriers for rectangular matrix multiplication , JOURNAL =. 2025 , NUMBER =. doi:10.1007/s00037-025-00264-9 , URL =

    work page doi:10.1007/s00037-025-00264-9 2025

  39. [39]

    Blum, Manuel , title =. J. Assoc. Comput. Mach. , issn =. 1967 , language =. doi:10.1145/321386.321395 , keywords =

    work page doi:10.1145/321386.321395 1967

  40. [40]

    Theory Comput

    Alman, Josh , TITLE =. Theory Comput. , FJOURNAL =. 2021 , PAGES =. doi:10.4086/toc.2021.v017a001 , URL =

    work page doi:10.4086/toc.2021.v017a001 2021

  41. [41]

    Alman, Josh and Vassilevska Williams, Virginia , TITLE =. SIAM J. Comput. , FJOURNAL =. 2023 , NUMBER =. doi:10.1137/19M124695X , URL =

    work page doi:10.1137/19m124695x 2023

  42. [42]

    Proceedings of the forty-seventh annual ACM symposium on Theory of Computing , pages=

    Fast matrix multiplication: limitations of the Coppersmith-Winograd method , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of Computing , pages=. 2015 , doi=

    work page 2015

  43. [43]

    Strassen, Volker , TITLE =. Numer. Math. , FJOURNAL =. 1969 , PAGES =. doi:10.1007/BF02165411 , URL =

    work page doi:10.1007/bf02165411 1969

  44. [44]

    Strassen, Volker , TITLE =. J. Reine Angew. Math. , FJOURNAL =. 1973 , PAGES =. doi:10.1515/crll.1973.264.184 , URL =

    work page doi:10.1515/crll.1973.264.184 1973

  45. [45]

    , TITLE =

    Bini, D. , TITLE =. Calcolo , FJOURNAL =. 1980 , NUMBER =. doi:10.1007/BF02575865 , URL =

    work page doi:10.1007/bf02575865 1980

  46. [46]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Fast deterministic chromatic number under the asymptotic rank conjecture , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    work page 2025

  47. [47]

    Proceedings of the 53rd EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2026) , series =

    Kronecker scaling of tensors with applications to arithmetic circuits and algorithms , author =. Proceedings of the 53rd EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2026) , series =. 2026 , note =. 2504.05772 , archivePrefix =

    work page arXiv 2026

  48. [48]

    First European Congress of Mathematics Paris, July 6--10, 1992: Vol

    Algebra and complexity , author=. First European Congress of Mathematics Paris, July 6--10, 1992: Vol. II: Invited Lectures (Part 2) , pages=. 1994 , organization=

    work page 1992

  49. [49]

    2026 SIAM Symposium on Simplicity in Algorithms (SOSA) , pages=

    Faster Convolutions: Yates and Strassen Revisited , author=. 2026 SIAM Symposium on Simplicity in Algorithms (SOSA) , pages=. 2026 , organization=

    work page 2026