The Strassen matrix multiplication is a simple but amazing recursion to beat the easy cubic bound. And the probabilistic algorithm for primality with Solovay drove complexity research into probabilistic computation and helped make modern cryptography possible.

--

Posted By Lance to Computational Complexity at 10/25/2008 06:16:00 AM