ACM Awards Knuth Prize to Pioneer for Advances in Algorithms and Complexity Theory

Contacts:

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

Printable PDF file
 

NEW YORK, September 15, 2014 – Richard J. Lipton has been selected as the winner of the 2014 Knuth Prize for inventing new computer science and mathematical techniques to tackle foundational and practical problems in a wide range of areas in graph algorithms, computation, communication, program testing, and DNA computing. The Knuth Prize is jointly presented 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 will be presented at the Foundations of Computer Science (FOCS) Conference in Philadelphia, PA, October 18-21, where Lipton will give the Knuth Prize Lecture.

Together with ACM A. M. Turing Award winner Robert Tarjan, Lipton developed the planar separator theorem. It shows that a small number of intersections can be efficiently found in any road network, which, when removed, will split the network into disconnected pieces of at most half its original size. This operation facilitates a very efficient “divide and conquer” approach to solving problems on such networks by breaking down a problem into two or more sub-problems of the same or related type.

Lipton pioneered the design of algorithms that make random choices in order to solve computational problems, particularly as a way to test programs. He confronted the “chicken and egg” problem that can occur when building software designed to solve a complex problem – how to check the answers that a program produces without a way to compute the correct answers. In solving complex algebraic problems, Lipton showed that it was sufficient to check a program by running it against itself on randomly chosen but related inputs and comparing the results for consistency.

Working with another ACM Turing Award recipient, Richard Karp, Lipton developed a fundamental theorem in circuit complexity. It demonstrated that NP-complete problems are unlikely to be efficiently solved by the best of algorithms even when given specially-designed hardware. This critically important class of problems in computational complexity is the subject of intensive research. A purely algorithmic solution to this problem has long been the holy grail of computer science, and is the object of a million-dollar challenge from the Clay Mathematics Institute.

Lipton was an early developer of communication complexity, the study of the number of bits of communication needed for agents to solve computational tasks. He and his co-authors developed a multi-party version based on analogues of “hat puzzles” in recreational mathematics. This work showed its relevance for understanding the complexity of computations, and gave surprising solutions to the problems that arise. Lipton is also one of the original pioneers in DNA computing, which uses the combination and replication of the vast numbers of DNA strands that fit in a test tube as a basis for parallel computation.

A professor of Computer Science at Georgia Institute of Technology, Lipton holds the Frederick G. Storey Chair in the College of Computing. He previously held faculty positions at Yale University, the University of California, Berkeley, and Princeton University. A former chief consulting scientist at Telcordia (formerly known as Bellcore), he was a founding director of a computer science research laboratory for the Panasonic Corporation. He received a Ph.D. degree 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. It 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, 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.