The 2008 Knuth Prize is awarded to Volker Strassen for his seminal and
influential contributions to efficient algorithms.
Volker Strassen's work has had enormous influence on both the theory
and practice of algorithm design. He has discovered some of the most
important algorithms used today on millions if not billions of
computers around the world. His algorithms include fast matrix
multiplication, integer multiplication, and a test for the primality
of integers. In 1969 Strassen discovered a novel way to multiply two
$n$ by $n$ matrices in $O(n^{2.81})$ time. This intricate yet simple
algorithm is the method of choice for multiplying dense matrices of
size 30 by 30 or more on machines today. Using this new matrix
multiplication routine, he was able to show that Gaussian elimination
is not optimal. With Bob Solovay he developed
the first provably fast randomized primality test. Variants of his
primality testing is used by machines on a daily basis for
cryptographic methods such as RSA and for data structures such as hash
tables. The primality test opened the world of probabilistic
algorithms to computer scientists. For his work on
primality testing and randomized algorithm he was the co-recipient of
the ACM Paris Kanellakis Theory and Practice Award. The
Schonhage-Strassen integer multiplication method algorithm held the
world record for the fastest multiplication algorithm for thirty five
years. In practice, it is still a standard tool for computing with
large numbers. Besides his very practical work, Strassen has
also proved fundamental theorems in statistics, including "Strassen's
law of the iterated logarithm" and the principle of strong
invariance. He is considered the founding father of algebraic
complexity theory with his work on the degree bound, connecting
complexity to algebraic geometry, and introduced fundamental notions
and results in bilinear complexity and tensor rank.