Matrix Multiplication

Multiply two $n\times n$ matrices over $\mathbb{C}$ exactly. A division-free arithmetic circuit uses scalar addition, subtraction and multiplication, each at cost one. Inputs and field constants are free. Results proved over every field also qualify because they hold over $\mathbb{C}$ .

Classic bound: $O(n^{2.371177+\varepsilon})$ (Dupont et al., preprint published August 17, 2026).

The bound has the form $O(n^{t+\varepsilon})$ . $t$ is the arithmetic exponent; lower is better. For every fixed $\varepsilon>0$ , one positive constant $C$ bounds a correct circuit’s cost by $C n^{t+\varepsilon}$ for every positive size $n$ . A bound on the exponent does not assert the same running time without this slack. Exact Lean statement.

What counts as Claimed: Published results for this problem without a qualifying repository review or Lean proof check.
What counts as Human Verified: This problem has no community repo with a qualifying review rule.
What counts as Lean Verified: A result shows here when we rebuild its Lean proof from source and check, with the Lean kernel, that it proves our exact problem statement.

Claimed Human Verified Lean Verified

Rank	Bound	Evidence levelLevel	Player	Date	Link
1	$O(n^{2.25+\varepsilon})$	First breakthrough	OpenAI	Oct 6	Source	OpenAI Oct 6

$t$ in $O(n^{t+\varepsilon})$ , lower is better $t$ in $O(n^{t+\varepsilon})$ linear scale, lower is better

ClaimedHuman VerifiedLean Verified

First breakthrough

t

(linear scale)

t=2:\ O(n^{2})

The dashed line marks the classic bound $O(n^{2.371177+\varepsilon})$ . The trivial lower bound $t=2$ ( $O(n^{2})$ ) is below this range.

Matrix Multiplication

$t$ in $O(n^{t+\varepsilon})$ , lower is better $t$ in $O(n^{t+\varepsilon})$ linear scale, lower is better

Relevant repos

Ask about Big O Speedrun

Matrix Multiplication

ttt in O(nt+ε)O(n^{t+\varepsilon})O(nt+ε), lower is betterttt in O(nt+ε)O(n^{t+\varepsilon})O(nt+ε)linear scale, lower is better

Relevant repos iWe list repositories that publish a result for this problem or accept improvements to it. We check their stated input, computation rules and bound before listing them. A listing does not imply that we checked their proof.

$t$ in $O(n^{t+\varepsilon})$ , lower is better $t$ in $O(n^{t+\varepsilon})$ linear scale, lower is better

Relevant repos