The asymptotically fastest algorithm for matrix multiplication takes time O(*n*^{ω}) for some value of ω. Here are the best known upper bounds on ω over time.

The latest improvements, the first in over 20 years, are due to Andrew Stothers and Virginia Vassilevska Williams. The latter gave an O(*n*^{2.3727})-time algorithm for multiplying matrices.

When will the sometimes-conjectured ω = 2 be reached? Certainly nothing wrong with taking a linear fit of this data, right?

So that would be around the year 2043. Unfortunately, the pessimist's exponential fit asymptotes to ω = 2.30041...

## No comments:

## Post a Comment