mapping accurate contingencies delivering probable wisdom composing quantitative understanding formulating definitive forecasts delivering calibrated insights mapping the future aggregating intelligent predictions predicting predictive insights exploring intelligent understanding crowdsourcing probable futures predicting intelligent forecasts formulating critical contingencies predicting accurate predictions computing contingent contingencies

Question

Metaculus Help: Spread the word

If you like Metaculus, tell your friends! Share this question via Facebook, Twitter, or Reddit.

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

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 ?

{{qctrl.predictionString()}}

Metaculus help: Predicting

Predictions are the heart of Metaculus. Predicting is how you contribute to the wisdom of the crowd, and how you earn points and build up your personal Metaculus track record.

The basics of predicting are very simple: move the slider to best match the likelihood of the outcome, and click predict. You can predict as often as you want, and you're encouraged to change your mind when new information becomes available.

The displayed score is split into current points and total points. Current points show how much your prediction is worth now, whereas total points show the combined worth of all of your predictions over the lifetime of the question. The scoring details are available on the FAQ.

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.

This question is not yet open for predictions.

Thanks for predicting!

Your prediction has been recorded anonymously.

Want to track your predictions, earn points, and hone your forecasting skills? Create an account today!

Track your predictions
Continue exploring the site

Community Stats

Metaculus help: Community Stats

Use the community stats to get a better sense of the community consensus (or lack thereof) for this question. Sometimes people have wildly different ideas about the likely outcomes, and sometimes people are in close agreement. There are even times when the community seems very certain of uncertainty, like when everyone agrees that event is only 50% likely to happen.

When you make a prediction, check the community stats to see where you land. If your prediction is an outlier, might there be something you're overlooking that others have seen? Or do you have special insight that others are lacking? Either way, it might be a good idea to join the discussion in the comments.