OpenFrontiers
Join
← Back to the index
OP-12018OpenComputational complexity

Dual matrix multiplication exponent (C15bC_{15b})

Dual matrix multiplication exponent: determine C15bC_{15b} or improve its bounds; the repository records >0.321334 (lower) and 1 (upper).

MSC 68Q17 · Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)MSC 15A69 · Multilinear algebra, tensor calculus

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

In algebraic complexity theory, for each real k≥0k \ge 0, let ω(k)\omega(k) denote the exponent for multiplying an n×nkn \times n^k matrix by an nk×nn^k \times n matrix. We define

α:=sup⁡{k≥0:ω(k)=2}.\alpha := \sup\{k \ge 0 : \omega(k) = 2\}.

Thus α\alpha is the largest aspect-ratio exponent for which rectangular matrix multiplication can still be performed in essentially quadratic arithmetic time. [LGU2018-def-omega] [LGU2018-def-alpha]

We define

C15b:=α.C_{15b} := \alpha.

The current best established range is

0.321334<C15b≤1.0.321334 < C_{15b} \le 1.

[WXXZ2024-alpha-0321334] [CLLZ2025-ub-1]

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

References (from the repository page)

  • [CLLZ2025] Christandl, Matthias; Le Gall, François; Lysikov, Vladimir; Zuiddam, Jeroen. Barriers for rectangular matrix multiplication. Computational Complexity 34 (2025), article 4. DOI: 10.1007/s00037-025-00264-9. Preprint: arXiv:2003.03019 PDF. Google Scholar

  • [CLLZ2025-ub-1] loc: arXiv PDF p.4, Figure 2 caption quote: “The red points are the best upper bounds on α\alpha, namely 11.”

  • [LG2012] Le Gall, François. Faster Algorithms for Rectangular Matrix Multiplication. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012), 514–523. DOI: 10.1109/FOCS.2012.80. Preprint: arXiv:1204.1111 PDF. Google Scholar

  • [LG2012-alpha-029462-030298] loc: arXiv PDF p.1, Abstract quote: “In this paper we show that α>0.30298\alpha>0.30298, which improves the previous record α>0.29462\alpha>0.29462 by Coppersmith (Journal of Complexity, 1997).”

  • [LG2012-applications] loc: arXiv PDF p.1, Abstract quote: “For example, we directly obtain a O(n2.5302)O(n^{2.5302})-time algorithm for the all-pairs shortest paths problem over directed graphs with small integer weights, improving over the O(n2.575)O(n^{2.575})-time algorithm by Zwick (JACM 2002), and also improve the time complexity of sparse square matrix multiplication.”

  • [LGU2018] Le Gall, François; Urrutia, Florent. Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 1029–1046. DOI: 10.1137/1.9781611975031.67. Preprint: arXiv:1708.05622 PDF. Google Scholar

  • [LGU2018-def-omega] loc: arXiv PDF p.3, §1.1 “Background” quote: “In analogy to the square case, the exponent of rectangular matrix multiplication, denoted ω(k)\omega(k), is defined as the minimum value such that this product can be computed using O(nω(k)+ϵ)O(n^{\omega(k)+\epsilon}) arithmetic operations for any constant ϵ>0\epsilon>0.”

  • [LGU2018-def-alpha] loc: arXiv PDF p.3, §1.1 “Background” quote: “α=sup⁡{k∣ω(k)=2}\alpha = \sup\{k \mid \omega(k)=2\}.”

  • [LGU2018-alpha-0172] loc: arXiv PDF p.3, §1.1 “Background” quote: “Coppersmith [8] showed in 1982 that ω(0.172)=2\omega(0.172)=2.”

  • [LGU2018-alpha-031389] loc: arXiv PDF p.4, §1.2 “Our results” quote: “α≥0.31389\alpha \ge 0.31389”

  • [WXXZ2024] Vassilevska Williams, Virginia; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei. New Bounds for Matrix Multiplication: from Alpha to Omega. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), 3792–3835. DOI: 10.1137/1.9781611977912.134. Preprint: arXiv:2307.07970 PDF. Google Scholar

  • [WXXZ2024-alpha-0321334] loc: arXiv PDF p.3, Introduction, paragraph beginning “In particular” quote: “In particular, we show that α>0.321334\alpha >0.321334 (improving upon the previous bound 0.313890.31389)”

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound >0.321334; best known upper bound 1. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
11 [CLLZ2025] Current best general upper bound. [CLLZ2025-ub-1]

Known lower bounds

Bound Reference Comments
00 Trivial: ω(0)=2\omega(0)=2 since multiplying an n×1n\times 1 matrix by a 1×n1\times n matrix is an outer product.
0.1720.172 [LGU2018] Coppersmith’s 1982 theorem yields ω(0.172)=2\omega(0.172)=2. [LGU2018-alpha-0172]
0.294620.29462 [LG2012] Previous record due to Coppersmith (1997), as recorded in Le Gall’s 2012 paper. [LG2012-alpha-029462-030298]
0.302980.30298 [LG2012] Le Gall’s 2012 improvement. [LG2012-alpha-029462-030298]
0.313890.31389 [LGU2018] Improvement from the fourth-power Coppersmith–Winograd analysis. [LGU2018-alpha-031389]
0.3213340.321334 [WXXZ2024] Current best published lower bound. [WXXZ2024-alpha-0321334]
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Dual matrix multiplication exponent ($C_{15b}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.