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.