OP-0028OpenAlgorithms and data structures

Is the exponent of matrix multiplication equal to 2?

Every improvement since 1969 has shaved digits off 2.37. Nobody can rule out 2 + o(1), and nobody can achieve it.

MSC 68W · Algorithms in computer science

Inferred from the community field; finer classification has not been reviewed.

0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Let $\omega$ be the infimum of all $t$ such that two $n \times n$ matrices over a field can be multiplied using $O(n^{t})$ arithmetic operations. Is $\omega = 2$ ?

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

Strassen's 1969 algorithm gave $\omega \le \log_2 7 \approx 2.807$ , ending the belief that $n^3$ was optimal. The laser method of Coppersmith and Winograd, refined by Stothers, Vassilevska Williams, Le Gall, Alman and others, has pushed the bound to roughly $2.3714$ .

Why it matters

The exponent controls the asymptotic complexity of matrix inversion, determinant, graph algorithms via algebraic techniques, and much of numerical linear algebra. It is also one of the few places where an algebraic-geometry construction directly yields an algorithm.

Known partial results

Lower bound: $\omega \ge 2$ trivially, since the output has $n^2$ entries. No better unconditional lower bound is known.
Upper bound: approximately $2.3714$ (Alman, Duan, Vassilevska Williams, Xu, Xu, Zhou, 2024).
Ambainis, Filmus and Le Gall proved that the laser method applied to the Coppersmith–Winograd tensor cannot itself reach $2$ , so a new construction is required.
Group-theoretic approaches (Cohn–Umans) reduce the problem to finding groups with specific simultaneous triple product properties; several natural candidate families have been ruled out.

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.

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.