The ACM

announced that Volker Strassen will receive the Knuth Prize for his algorithmic work, most notably on primality, matrix multiplication and integer multiplication. The

Knuth Prize is given for major contributions over an extended period of time. The winner gives a Knuth Prize lecture and Strassen will give his at SODA.

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.

Congrats to Strassen!

ReplyDeleteA question is, does Knuth have a say on who gets the Knuth award?

Herzliche Glückwünsche, Volker!

ReplyDeleteWolf