Definition of matrix-multiplication exponent $\omega$

Question

Colloquially, the definition of the matrix-multiplication exponent $\omega$ is the smallest value for which there is a known $n^{\omega}$ matrix-multiplication algorithm. This is not acceptable as a formal mathematical definition, so I guess the technical definition is something like the infimum over all $t$ such that there exists a matrix-multiplication algorithm in $n^t$.

In this case, we cannot say there is an algorithm for matrix-multiplication in $n^{\omega}$ or even $n^{\omega + o(1)}$, merely that for all $\epsilon > 0$ there exists an algorithm in $n^{\omega + \epsilon}$. Often, however, papers and results which use matrix-multiplication will report their cost as simply $O(n^{\omega})$.

Is there some alternate definition of $\omega$ that permits this usage? Are there any results that guarantee that an algorithm of time $n^{\omega}$ or $n^{\omega + o(1)}$ must exist? Or is the usage $O(n^{\omega})$ simply sloppy?

Answer 1

The matrix multiplication exponent being $\omega$ does not guarantee that there is an algorithm that runs in time $O(n^\omega)$, but only that for each $\epsilon > 0$, there is an algorithm that runs in $O(n^{\omega+\epsilon})$. Indeed if you can find an algorithm that runs in time $O(n^2 \mathrm{polylog}(n))$, then this shows that $\omega = 2$.

You can find the formal definition in the book Algebraic Complexity Theory by Peter Bürgisser, Michael Clausen, Amin Shokrollahi.

Answer 2

A minor comment that's too long to be a comment:

Sometimes when you have a problem for which there is an algorithm with running time $O(n^{k+\epsilon})$ for every $\epsilon>0$, there is an algorithm with running time $n^{k+o(1)}$.

For example, sometimes you get algorithms that go like $f(1/\epsilon)n^{k+\epsilon}$ for some fast growing function $f$ (like $2^{2^{1/\epsilon}}$). If you set $f(1/\epsilon)$ to (say) $\log n$, then $\epsilon$ will be o(1). In the example with $f(1/\epsilon)$ being $2^{2^{1/\epsilon}}$, you can choose $1/\epsilon$ to be $\log \log \log n$, which gives $\epsilon = 1/ (\log \log \log n)$, which is o(1). So the final running time of this algorithm will be $n^{k+o(1)}$, since $\log n$ is also $n^{o(1)}$.

Answer 3

It is well-known the result of Coppersmith and Winograd that $O(n^{\omega})$-time cannot be realized by any single algorithm. But I've read that they restricted to algorithms based on Strassen-like bilinear identities, so I don't know for sure since the paper is behind a paywall.

Answer 4

I do not agree with your statement in the question that $\omega$ is not well-defined by "the smallest value for which there is a known $n^ω$ matrix-multiplication algorithm." When people are using this constant, it is because their algorithm relies on a matrix multiplication, and by a complexity $n^\omega$, they mean "the optimal complexity of our algorithm is given by the optimal algorithm for matrix multiplication."

I am not saying that it is not possible to define $\omega$ otherwise (e.g. saying that $\omega$ is the best achievable complexity).

Btw, the best known upper bound for matrix multiplication has just been improved to $2.3737$ if I am not mistaken.