ACM Awards Knuth Prize to Creator of Problem-Solving Theory and Algorithms

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

Contacts:

Paul Beame				Virginia Gold
ACM SIGACT Chair				ACM
206-543-5114				212-626-0505
[email protected]				[email protected]

Printable PDF file

NEW YORK, April 4, 2013 – The 2013 Donald E. Knuth Prize will be awarded to Gary L. Miller of Carnegie Mellon University for algorithmic contributions to theoretical computer science. His innovations have had a major impact on cryptography as well as number theory, parallel computing, graph theory, mesh generation for scientific computing, and linear system solving.  The Knuth Prize is jointly presented by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the IEEE Computer Society Technical Committee on the Mathematical Foundations of Computing (TCMF).  It will be presented at the Symposium on Theory of Computing (STOC 2013) in Palo Alto, CA, June 1-4, where Miller will give the Knuth Prize Lecture. 

In his 1975 paper on computational number theory, Miller introduced the first efficient algorithm to test whether a number is prime (divisible evenly only by 1 and itself).  The generation of large primes is an essential part of the RSA public key cryptosystem, on which much of today’s Internet commerce depends. The efficiency of Miller’s algorithm depends on the truth of a widely-believed (but still not proved) mathematical hypothesis (known as the Riemann Hypothesis).  In 1976, Michael O. Rabin showed how randomization could be used to turn Miller’s algorithm into one whose efficiency did not rely on any unproven hypotheses.  The resulting Miller-Rabin test is now the main method used in practice for RSA encryption keys. Miller and Rabin were part of a group that received ACM's 2003 Paris Kanellakis Theory and Practice Award for methods to improve cryptography.

Miller also made significant contributions to the theory of isomorphism testing—the problem of telling whether two structures are the same except for the labeling of their components.  He showed the equivalence of many different isomorphism problems to the still-open problem of graph isomorphism, and identified many special cases that could be solved efficiently. These included the problem of testing isomorphism for a special case known as bounded-genus graphs, a result he obtained with John Reif in 1980.  In 1985, in another collaboration with Reif, Miller invented the concept of "parallel tree contraction." This is one of the most fundamental primitives in parallel algorithm design with wide applications to graph theoretical and algebraic problems. 
 
In 1984, Miller moved into the area of scientific computing. He set up the theoretical foundations for mesh generation, and was the first to design meshing algorithms with near-optimal runtime guarantees.  His subsequent research led to his breakthrough 2010 results with Ioannis Koutis and Richard Peng that currently provide the fastest algorithms—in theory and practice—for solving "symmetric diagonally dominant" linear systems. These systems have important applications in image processing, network algorithms, engineering, and physical simulations.  

A professor of Computer Science at Carnegie Mellon University, Miller earned a Ph.D. degree from the University of California, Berkeley.  He previously held faculty positions at the University of Waterloo, the University of Rochester, Massachusetts Institute of Technology, and the University of Southern California.
 
The Knuth Prize is named in honor of Donald Knuth of Stanford University who has been called the "father" of the analysis of algorithms. It is is given annually by ACM SIGACT and the IEEE Computer Society TCMF, and includes a $5,000 award. 

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.