Or at least it's order of magnitude.
I've only ever heard it described as "huge", and a google search turned up nothing.
Also, given that the Strassen algorithm has a significantly greater constant than Gaussian Elimination, and that Coppersmith-Winograd is greater still, are there any indications of what constant an O(n^2) matrix multiplication algorithm might have?
Best Answer
In your second question, I think you mean "naive matrix multiplication", not "Gaussian elimination".
Henry Cohn et al had a cute paper that relates fast matrix multiply algorithms to certain groups. It doesn't do much for answering your question (unless you want to go and prove the conjectured results =), but it's a fun read.
Also, to back up harrison, I don't think that anyone really believes that there's an $O(n^2)$ algorithm. A fair number of people believe that there is likely to be an algorithm which is $O(n^{2+\epsilon})$ for any $\epsilon > 0$. An $O(n^2 \log n)$ algorithm would fit the bill.
edit: You can get a back-of-the-envelope feeling for a lower bound on the exponent of Coppersmith-Winograd based on the fact that people don't use it, even for n on the order of 10,000; naive matrix multiplication requires $2n^3 + O(n^2)$ flops, and Coppersmith-Winograd requires $Cn^{2.376} + O(n^2)$. Setting the expressions equal and solving for $C$ gives that the two algorithms would have equal performance for n = 10,000 (ignoring memory access patterns, implementation efficiency, and all sorts of other things) if the constant were about 627. In reality, it's likely much larger.