Communications of the ACM
ACM Awards Knuth Prize to Pioneer for Advances in Algorithms and Complexity Theory
Richard J. Lipton has been selected to receive the 2014 Knuth Prize for inventing techniques to tackle foundational and practical problems in a wide range of areas in graph algorithms, computation, communication, program testing, and DNA computing.
Credit: Georgia University of Technology
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.
From ACM
View Full Article
No entries found