Richard Lipton Wins Knuth Prize

Georgia Tech professor and fellow blogger Richard Lipton will receive the 2014 Knuth Prize at the upcoming FOCS conference in Philadelphia. The Knuth Prize is given jointly by the ACM SIGACT and the IEEE TC-MFCS for major research accomplishments and contributions to the foundations of computer science over an extended period of time.

Lipton's research has major results across a large spectrum of theoretical computer science from probabilistic algorithms to DNA computing to communication complexity. I'd like to highlight a couple of his papers in computational complexity hugely influential, including much of my own research.

Richard Karp and Lipton showed that if NP has non-uniform polynomial-size circuits then the polynomial-time hierarchy collapses. The result, and its successors, are a powerful tool, used to show a number of interesting hypotheses are not likely to happen, and plays an important role itself in circuit lower bounds and pseudorandomness. Most importantly Karp-Lipton showed gave the strongest evidence that NP does not have small circuits, justifying the circuit lower bound approach to separating complexity classes.

In lesser known but perhaps even more influential work, Lipton developed a notion of program testing and showed how to test the permanent function, a result that directly led to the surprising power of interactive proofs. This algebraic characterization of hard problems led us to IP = PSPACE, MIP = NEXP and the PCP theorem.

Again this just covers a sliver of his impressive canon of research. Congrats Dick!