ACM SIGACT 2008 Knuth Prize Recognizes Strassen for Contributions to Efficient Algorithm Design

acm
Association for Computing Machinery
Advancing Computing as a Science & Profession

Contacts:

 

Richard Ladner				Virginia Gold
ACM SIGACT Chair				ACM
206-543-9347				212-626-0505
[email protected]				[email protected]

 

NEW YORK, October 23, 2008 – The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) will present its 2008 Knuth Prize to Volker Strassen of the University of Konstanz in Germany, for his contributions to the theory and practice of algorithm design.  Strassen’s innovations enabled fast and efficient computer algorithms, the sequence of instructions that tells a computer how to solve a particular problem.  His discoveries resulted in some of the most important algorithms used today on millions if not billions of computers around the world, and fundamentally altered the field of cryptography, which uses secret codes to protect data from theft or alteration.  The Knuth Prize, named in honor of Donald Knuth of Stanford University who has been called the "father" of the analysis of algorithms, will be presented at the ACM- SIAM Symposium on Discrete Algorithms (SODA), January 4-6, 2009, in New York, NY. 

Strassen’s algorithms include fast matrix multiplication, integer multiplication, and a test for the primality of integers.  The discovery of provably fast algorithms to determine whether a number is prime or composite profoundly changed the cryptography field.  These primality tests are now performed billions of times a day on machines worldwide to apply cryptographic methods that make data secure.  The primality test opened the world of probabilistic algorithms to theoretical computer scientists, presenting an innovative way to solve sharing problems, which are often used in fault tolerant systems.  For his work on primality testing and randomized algorithms Strassen was the co-recipient of the 2003 ACM Paris Kanellakis Theory and Practice Award. 

Modern primality tests involve multiplying many large integers together.  For thirty five years, the Schonhage-Strassen integer multiplication method algorithm held the world record for the fastest multiplication algorithm. It is still a standard tool for computing with very large numbers.

In 1969, Strassen discovered a novel way to multiply two matrices, a critical element of linear algebra that is pervasive throughout the sciences.  It is an intricate yet simple algorithm that remains the method of choice for multiplying dense matrices of size 30 by 30 or more on machines today. Using this new matrix multiplication routine, Strassen was able to show that Gaussian elimination (an efficient algorithm for solving systems of linear equations) is not an optimal solution.  Few students in computer science have not encountered Strassen's multiplication algorithm in their undergraduate program. Researchers in algorithm design have regularly used his method to improve the run time of their algorithms.

In addition to his very practical work, Strassen has 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.  He also introduced fundamental notions and results in bilinear complexity and  tensor rank.

The Knuth Prize, given every year and a half by ACM SIGACT and the IEEE Technical Committee on the Mathematical Foundations of Computer Science, includes a $5,000 award.  It is presented in honor of Donald Knuth, Professor Emeritus at Stanford University, who is best known for his ongoing multivolume series, The Art of Computer Programming, which played a critical role in establishing and defining computer science as a rigorous intellectual discipline.  The Knuth Prize was first awarded to Andrew C. - C. Yao, who went on to win ACM’s 2000 A.M. Turing Award, considered the “Nobel Prize of computing.”

 

About ACM

ACM, the Association for Computing Machinery www.acm.org, is the world’s largest educational and scientific computing society, uniting computing educators, researchers and professionals to inspire dialogue, share resources and address the field’s challenges. ACM strengthens the computing profession’s collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.  

 

 About SIGACT

The ACM Special Interest Group on Algorithms and Computation Theory http://sigact.acm.org fosters and promotes the discovery and dissemination of high quality research in the domain of theoretical computer science.  The field includes algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.