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

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, Ore.

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 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 ACM 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).

Contacts:

Paul Beame

ACM SIGACT Chair

206-543-5114

[email protected]

 

Virginia Gold

ACM

212-626-0505

[email protected]