Preview for editing tables

In this editor you can enter or edit tables in YAML format, and you can get a preview of how numberdb would render it. You cannot save changes here. Once everything looks good, upload it to the git repository numberdb-data.
— preview —
Exponent of matrix multiplication complexity
edit on github
Numbers
$\omega$
[2, 2.3728596]
Definition
$\omega$ is the smallest real number such that any two $n\times n$ matrices can be multiplied in $O(n^{\omega+\varepsilon})$ field operations for any $\varepsilon > 0$.
Comments
(1)
The trivial matrix multiplication algorithm runs in $O(n^3)$, which proves $2 \leq \omega \leq 3$.
(2)
This trivial upper bound was improved upon many times [4].
Strassen [2] proved $\omega \leq \log_2(7) \leq 2.8074$.
Alman and Vassilevska--Williams [1] proved the most recent bound $\omega \leq 2.3728596$.
References
[1]
Josh Alman and Virginia Vassilevska Williams, "A Refined Laser Method and Faster Matrix Multiplication", 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) (arXiv)
[2]
Volker Strassen, "Gaussian elimination is not optimal", Numerische Mathematik. 13 (4): 354-356, 1969. (doi)
Links
Data properties
Entries are of type: real number
Sources of data: [1]