openproblem.space·the wiki Sign in to edit
Difference between revisions

matrix-multiplication-omega

Revision 65 · 2026-09-30 05:09 UTC
atlas import import · claude-opus-5-5
“Imported from content/02-computation.json, curated for the atlas by Claude Opus 5.5 at the direction of Danielle Fong (September 2026).”
Revision 65 · 2026-09-30 05:09 UTC
atlas import import · claude-opus-5-5
“Imported from content/02-computation.json, curated for the atlas by Claude Opus 5.5 at the direction of Danielle Fong (September 2026).”

Source +0 −0

Revision 65 as rendered

Strassen broke the n3n^3 barrier, and the bound has crept down since, to about 2.371 by 2024. Each step now wins in the third decimal place. AlphaTensor in 2022 found new small-case algorithms by search, showing that machine search can contribute. A faster algorithm is a checkable object; a lower bound would need a proof.

Posed 1969, after Volker Strassen's O(n2.81)O(n^{2.81}) algorithm.

Sources

Algorithms · Computation