ACM, IEEE Taps Lipton for Prestigious Knuth Prize

Richard Lipton, a professor and the Frederick G. Storey Chair in Computing in the School of Computer Science, was recently named the winner of the 2014 Knuth Prize for his contributions to the foundations of computer science.

Richard Lipton, a professor and the Frederick G. Storey Chair in Computing in the School of Computer Science, added a second major award to his credentials this year as he was recently named the winner of the 2014 Knuth Prize for his contributions to the foundations of computer science.

In receiving the award, Lipton was cited 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). The award will be presented at the Foundations of Computer Science (FOCS) Conference in Philadelphia, PA, from Oct. 18 to 21, where Lipton will give the Knuth Prize Lecture.

Earlier this year, Lipton was elected to the 2014 class of the American Academy of Arts and Sciences. With the Knuth Prize, Lipton joins a short list of extraordinary computer scientists.

“The Knuth Prize means a great deal,” Lipton said. “It is very exciting to be recognized by your peers for work that spans over 40 years. I feel very special and thankful to have been selected.” 

Lance Fortnow, chair of the School of Computer Science, offered his praise:

"Dick's work has had a major impact in quite diverse areas across theoretical computer science and has heavily influenced many researchers including myself. I can think of no one more deserving of this award."

In presenting the award, the selection committee cited:

  • Lipton’s development of the planar separator theorem. Working with Turing Award winner Robert Tarjan, Lipton created a “divide-and-conquer” approach to solving difficult network problems by breaking problems into two or more sub-problems of the same or related type.
  • Lipton’s pioneering work in the design of algorithms that make random choices in order to solve computational programs. He showed that when working with complex algebraic problems, it was sufficient to check a program by running it against randomly chosen but related inputs and comparing the results for consistency.
  • His development of a fundamental theorem in circuit complexity with Richard Karp, another Turing Award recipient. This demonstrated that NP-complete problems are unlikely to be solved by the best algorithms even with specialized hardware.
  • His status as an early developer of communication complexity, the study of the number of bits of communication needed for agents to solve computational tasks, and 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.

The Knuth Prize is named in honor and recognition of Turing Award winner Donald Knuth, professor emeritus at Stanford University. Knuth is well-known for his ongoing multivolume series, The Art of Computer Programming, which played a critical role in establishing and defining computer science as a rigorous, intellectual discipline.

Lipton earned his undergraduate degree in mathematics from Case Western Reserve University and his Ph.D. from Carnegie Mellon University. He taught at Yale, the University of California in Berkeley and Princeton before joining the Georgia Tech faculty in 2000.

Lipton explores one of the most daunting puzzles in computation theory in his blog Gödel’s Lost Letter and P=NP and recently published his second book based on the blog, People, Problems, and Proofs: Essays from Gödel's Lost Letterwhich he co-authored with Kenneth W. Regan of the University of Buffalo.