Submit progress

on Dual matrix multiplication exponent ($C_{15b}$)

The statement

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

\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

C_{15b} := \alpha.

The current best established range is

0.321334 < C_{15b} \le 1.

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

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.