2 ms·
I have this feeling that the lower bound for matrix multiplication is heading towards some transcendental number that we don’t know about, or a function of one
by hinkley 3y ago
I have this feeling that the lower bound for matrix multiplication is heading towards some transcendental number that we don’t know about, or a function of one we do.
I wonder if finding the answer to that will clue someone in to what the optimal solution is, by pointing to some hidden structure to the problem that we have all missed.
- staplung 3y agoMaybe instead they'll be like Feigenbaum constants: apparently universal constants that we don't really understand. For instance, we don't even know for sure that Feigenbaum constants are irrational, though mathematicians who study them strongly suspect they're transcendental. https://en.wikipedia.org/wiki/Feigenbaum_constants https://en.wikipedia.org/wiki/Feigenbaum_constants
- zeroonetwothree 3y agoI feel it’s more likely there is an n^2 algorithm using some radically different approach.
- bobbylarrybobby 3y agoI would assume n^(2+epsilon) where epsilon can be made arbitrarily small, but must be positive.