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

Carnegie Mellon's Miller Cited as Pioneer in Theoretical Computer Science

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 | |||

beame@cs.washington.edu |

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.

# # #