Matrix Multiplication Problem

Open complexity problem: how few operations multiplying two n×n matrices takes, tracked by the exponent ω from Strassen's 2.807 to today's galactic records.

Specifications & Metrics

type

Problem

symbol

ω

best bound

O(n^2.371339)

Core Principles & Analysis

• The best proven bound on the matrix multiplication exponent ω is O(n^2.371339), given by Alman, Duan, Williams, Xu, Xu, and Zhou as of September 2025.
• That record algorithm is a galactic algorithm: its constants are so large it cannot be realized practically.
• Victor Pan proposed feasible sub-cubic algorithms with an exponent slightly above 2.77 that trade a worse exponent for a much smaller hidden constant.

Sources

• Wikipedia: Matrix multiplication algorithm