OP-00181 Partially resolved

Minimal asymptotic rank of the small Coppersmith–Winograd tensor

Let $e_0, e_1, e_2$ be the standard basis of $\mathbb{C}^3$ and $$T = \sum_{i=1}^{2} \left(e_0 \otimes e_i \otimes e_i + e_i \otimes e_0 \otimes e_i + e_i \otimes e_i \otimes e_0\right) \in \mathbb{C}^3 \otimes \mathbb{C}^3 \otimes \mathbb{C}^3,$$ the small Coppersmith–Winograd tensor $\mathrm{cw}_2$. Let $\widetilde R(T) = \lim_{k \to \infty} R(T^{\otimes k})^{1/k}$ be its asymptotic rank, where $R$ is tensor rank over $\mathbb{C}$ and $T^{\otimes k} \in (\mathbb{C}^{3^k})^{\otimes 3}$ the $k$-th Kronecker power. Coppersmith and Winograd showed that $T$ has border rank $4$, so $3 \le \widetilde R(T) \le 4$, the lower bound because $T$ is concise. Their analysis shows that $\widetilde R(T) = 3$ would imply that the exponent of matrix multiplication is $2$. Its Kronecker square has border rank $16$ (Conner, Huang and Landsberg). Alman and Li proved $\widetilde R(T) < 3.931$.

Problem. Is $\widetilde R(T) = 3$?

Source: Bläser (2013), Problem 9.8, for every q, after Coppersmith and Winograd (1990), §11; stated for q = 2 by OpenProblemsInNLA.

Imported from github.com/ajt60gaibb/OpenProblemsInNLA.

Classification

Primary: AG — Algebraic Geometry
Secondary: NA
Keywords: asymptotic rank, Coppersmith–Winograd tensors, matrix multiplication, OpenProblemsInNLA
Literature checked: Oct. 8, 2026 by clemens-admin

References

@book{blaser2013,
  author    = {Bl{\"a}ser, Markus},
  title     = {Fast Matrix Multiplication},
  series    = {Theory of Computing Library, Graduate Surveys},
  number    = {5},
  publisher = {Theory of Computing Library},
  year      = {2013},
  pages     = {1--60},
  doi       = {10.4086/toc.gs.2013.005},
}
@article{coppersmith1990,
  author  = {Coppersmith, Don and Winograd, Shmuel},
  title   = {Matrix multiplication via arithmetic progressions},
  journal = {J. Symbolic Comput.},
  volume  = {9},
  number  = {3},
  year    = {1990},
  pages   = {251--280},
  doi     = {10.1016/S0747-7171(08)80013-2},
}
@inproceedings{alman2026,
  author        = {Alman, Josh and Li, Baitian},
  title         = {Asymptotic Rank Speedup Theorems, Revisited},
  booktitle     = {41st Computational Complexity Conference (CCC 2026)},
  editor        = {Moshkovitz, Dana},
  series        = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume        = {383},
  publisher     = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year          = {2026},
  pages         = {36:1--36:42},
  doi           = {10.4230/LIPIcs.CCC.2026.36},
  eprint        = {2605.21738},
  archivePrefix = {arXiv},
}
@article{conner2023,
  author        = {Conner, Austin and Huang, Hang and Landsberg, J. M.},
  title         = {Bad and Good News for {S}trassen's Laser Method: Border Rank of {${\rm Perm}_3$} and Strict Submultiplicativity},
  journal       = {Found. Comput. Math.},
  volume        = {23},
  number        = {6},
  year          = {2023},
  pages         = {2049--2087},
  doi           = {10.1007/s10208-022-09579-3},
  eprint        = {2009.11391},
  archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ac04,
  author       = {Townsend, Alex},
  title        = {{AC-04}: Minimal asymptotic rank of the small Coppersmith–Winograd tensor},
  howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
  year         = {2026},
  url          = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/arithmetic-and-complexity/AC-04/README.md},
  note         = {Read at commit b8c7852, 2026-10-07},
}

Resolution claims

Non-coordinate residual extraction v1 GitHub ↗

Sidney Holden

The asymptotic rank of the small Coppersmith--Winograd tensor $P=\mathrm{cw}_2$ over $\mathbb C$ satisfies $\widetilde R(P)<3.876919161$. The new ingredient is a three-dimensional isotropic space of matrices that is not obtained by selecting coordinates. It lets a literal copy of $P$ survive inside a tensor retained from two Coppersmith--Winograd residuals: for positive odd $\ell_1,\ell_2$ the retained tensor is $P\otimes Z_{\ell_1,\ell_2}$, where $Z_{\ell_1,\ell_2}$ …

Partial resolution · not verified · fidelity not established · posted on GitHub 14 Sep 2026

Status history

When	Change	By	Reason
2026-10-09	Open → Partially resolved	The registry's curators	Non-coordinate residual extraction v1 recorded from OpenProblemsInNLA @ eb7c9d6, report/AC01_round3_report.pdf.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00181, "Minimal asymptotic rank of the small Coppersmith–Winograd tensor", clopen.solutions.