Your submission is now in Draft mode.

Once it's ready, please submit your draft for review by our team of Community Moderators. Thank you!

Submit Essay

Once you submit your essay, you can no longer edit it.

Pending

This content now needs to be approved by community moderators.

Submitted

This essay was submitted and is waiting for review.

What will be the exponent of the fastest known polynomial-time matrix multiplication algorithm in 2029?

Question

The computational complexity class of an algorithm is a measure of how the runtime increases as the input becomes larger. Often, these are written in big-O notation, where an algorithm running in time means that there is some constant for which the runtime will never exceed for an input of length .

In the case of matrix multiplication, the best-known algorithm runs in polynomial time; multiplication of two square n×n matrices runs in time for some . Over time, the smallest known ω has been decreasing - faster algorithms have been discovered.

Naive matrix multiplication, from directly evaluating the sum of the definition, has complexity in time. In 1969, Strassen discovered Strassen's algorithm, which has complexity in . By 1990, the Coppersmith-Winograd algorithm was discovered, which has complexity in ; this has been improved slightly since, with the current best-known algorithm being Le Gall's, which has complexity in and was discovered in 2014.

The best known lower bound on matrix multiplication is ; it is known that there is no algorithm faster than this. So further improvement on Le Gall's algorithm has not yet been ruled out.

In 2029, what will be the smallest for which there is known to exist an algorithm to multiply two square n×n matrices which has complexity in ?

Make a Prediction

Prediction

Note: this question resolved before its original close time. All of your predictions came after the resolution, so you did not gain (or lose) any points for it.

Note: this question resolved before its original close time. You earned points up until the question resolution, but not afterwards.

Current points depend on your prediction, the community's prediction, and the result. Your total earned points are averaged over the lifetime of the question, so predict early to get as many points as possible! See the FAQ.