The naïve way to
multiply square
matrices runs in time O(n^3); for many years no one suspected this was less than optimal. But
Strassen discovered an algorithm which runs in time O(n^2.81...). This was
very surprising, and sparked new interest in matrix multiplication
algorithms. Today the best known algorithm runs in time O(n^2.31...) (although with such a large constant factor that it is unclear if it is useful in the
Real World), but nothing is known about a
lower bound. In fact, it is not known that matrix multiplication cannot be done in O(n^2) (the size of the input).
The detailed algorithm is described in my writeup under matrix multiplication.