# ACM Group to Recognize Innovations that Are Advancing Power of Computing

Knuth and Gödel Prizes to Be Awarded for New Concepts for Mathematical Proofs and Speeding Solutions to Complex Computing Tasks

Paul Beame |
Virginia Gold |

ACM SIGACT Chair |
ACM |

206-543-5114 | 212-626-0505 |

beame@cs.washington.edu | vgold@acm.org |

Printable PDF file

**NEW YORK, May 27, 2015** – With the emergence of massive computing
tasks that arise in the world of web applications and networks, an ACM group
will recognize László Babai, Daniel A. Spielman, and Shang-Hua Teng for
advancing the power of computing. Babai will receive the Donald
E. Knuth Prize for his fundamental contributions to algorithm design and
computational complexity, including pioneering a new understanding of the
notion of mathematical proof. Spielman and Teng will receive the Gödel Prize for improvements
in the running time for core problems in algorithmic graph theory. The awards will be presented at the ACM
Symposium on the Theory of Computing (STOC 2015), June 14-17, in Portland, OR.

Knuth Prize winner Babai is recognized for his many visionary contributions, which have transformed the landscape of computing theory. He led the way in combining interaction and randomness to broaden the millennia-old concept of mathematical proof. His work on the power of interactive proofs with multiple provers led to the discovery of the fundamental implications of the hardness of approximately solving optimization problems. The methods for interactive proofs introduced by him and his co-authors also became a foundation for the development of locally testable codes and the study of property testing.

Gödel Prize recipients Spielman and Teng addressed the challenge of improving the efficiency of graph algorithms. Their result delivered a new, extremely powerful algorithmic primitive or basic building block – nearly linear time electrical flow computations – which resolved an outstanding problem in numerical linear algebra. Their approach has been used to obtain substantial improvements in the running time for several core problems in algorithmic graph theory, which are used to model real-world problems.

László
Babai is the George and Elizabeth Yovovich Professor of Computer Science and Mathematics at the University
of Chicago. He previously was a faculty member at Eötvös Loránd University. He
is a founder of the Budapest Semesters in Mathematics program and of the
journal *Combinatorica*, and is founder
and editor-in-chief of the open access journal *Theory of Computing*. He is a recipient of the Erdös Prize, the 1993
Gödel Prize, and is a Fellow of the American Academy of Arts and Sciences. The
author of more than 180 academic papers, he received a Ph.D. degree from the
Hungarian Academy of Sciences.

Daniel A. Spielman is the Henry Ford II Professor of Computer Science, Mathematics, and Applied Mathematics at Yale University. Previously he was a postdoctoral student at University of California, Berkeley, and a professor at Massachusetts Institute of Technology. A Gödel Prize recipient in 2008, he received the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2009 Fulkerson Prize, the 2010 Nevanlinna Prize, and the 2014 Polya Prize. He was an inaugural Simons Investigator Award recipient, and won a MacArthur Fellowship. A Fellow of ACM, he received a B.A. degree in Mathematics and Computer Science from Yale, and a Ph.D. degree in Applied Mathematics from MIT.

Shang-Hua Teng is the Seeley G. Mudd Professor of Computer Science and Mathematics at the University of Southern California. Previously at Boston University, the University of Illinois, Urbana-Champaign, the University of Minnesota, and MIT, he also worked at Akamai and Xerox PARC, and consulted for Microsoft, Intel, IBM, and NASA. He is an ACM Fellow, Sloan Fellow, and a Simons Investigator, and is the recipient of the 2008 Gödel Prize and the 2009 Fulkerson Prize. He earned a B.S. degree from Shanghai Jiao Tong University, an M.S. degree from the University of Southern California, and a Ph.D. from Carnegie Mellon University.

The
Knuth Prize is named in honor of Donald Knuth of Stanford University who has
been called the "father" of the analysis of algorithms. The
award is presented annually by ACM’s Special Interest Group on Algorithms and
Computation Theory (SIGACT) and the
IEEE Computer Society Technical Committee on the Mathematical Foundations of
Computing (TCMF). It recognizes outstanding
contributions to the foundations of computer science by individuals for their overall impact in the field
over an extended period__,__
and includes a $5,000 award.

The
Gödel Prize is named in honor of Kurt Gödel, who was born in Austria-Hungary
(now the Czech Republic) in 1906. Gödel's
work has had immense impact upon scientific and philosophical thinking in the
20^{th} century. The award is presented annually by
SIGACT and the European Association for Theoretical Computer Science
(EATCS). It recognizes major
contributions to mathematical logic and the foundations of computer science and
includes an award of $5,000.

**About ACM **

ACM,
the Association for Computing Machinery, 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** **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. ** **

**About
EATCS**

The European Association for Theoretical Computer Science is an international organization aimed at promoting research in the wide field of the foundations of computer science (ranging from formal languages, abstract computation models, algorithm design and complexity analysis, to applications of logic and semantics in programming). It facilitates the exchange of ideas and results among computer scientists, in particular through the organization of the annual International Conference on Automata, Languages and Programming (ICALP).