Can two n x n matrices be multiplied in O(n^2.15) time?
34
230
650
2087
66%
chance


Close date updated to 2087-11-13 6:59 pm

Get Ṁ200 play money
Sort by:
bought Ṁ10 of NO


The possibility of achieving O(n^2.15) time for multiplying two n x n matrices is an ongoing research topic in computational complexity theory. While there is no definitive answer as to whether or not it is possible, there are several mathematicians and computer scientists who believe that it may be achievable.

The Strassen algorithm, the fastest known algorithm for matrix multiplication with a time complexity of O(n^2.807), was discovered in 1969.

Since then, there have been many attempts to improve upon this algorithm, but no one has yet been able to achieve a time complexity better than O(n^2.373).

https://people.csail.mit.edu/virgi/matrixmult-f.pdf

predicts YES

I am also curious why the soon end date - it seems like we won't know by then unless you know something I don't.

bought Ṁ10 of YES

Can two n x n matrices be multiplied in O(n^2.15) time?, 8k, beautiful, illustration, trending on art station, picture of the day, epic composition