Richard Lipton

Richard Jay Lipton (born 1946) is an American computer scientist who holds the Frederick G. Storey chair in computing at the Georgia Institute of Technology, where he has been associate dean of research. He took an undergraduate degree in mathematics at Case Western Reserve University in 1968 and a doctorate at Carnegie Mellon University in 1973 with a dissertation on synchronization primitive systems. He taught at Yale, Berkeley and Princeton before moving to Georgia Tech in 2000. His work spans theoretical computer science, cryptography and DNA computing. With Richard Karp he proved in 1980 that if satisfiability can be solved by polynomial-size Boolean circuits, the polynomial hierarchy collapses to its second level, a result known as the Karp-Lipton theorem. He also developed reduction methods that simplify correctness proofs of parallel programs and studied models for restricting database queries so that private information is not leaked. He was elected to the National Academy of Engineering in 1999.