Professor of Computer Science, University of California
Richard M. Karp was born in Boston, Massachusetts in 1935 and was educated at the Boston Latin School and Harvard University, where he received his Ph.D. in Applied Mathematics in 1959. From 1959 to 1968he was a member of the Mathematical Sciences Department at the IBM Thomas J. Watson Research Center. From 1968 to 1994 he was a professor at the University of California, Berkeley. From 1988 to 1995 he was also associated with the International Computer Science Institute in Berkeley. In 1994 he retired from Berkeley and was named University Professor (Emeritus). In 1995 he moved to the University of Washington, where he has appointments in Computer Science and Molecular Biotechnology. The unifying theme in Karp's work has been the study of combinatorial algorithms. His 1972 paper "Reducibility Among Combinatorial Problems," demonstrated the wide applicability of the concept of NP-completeness. Much of his subsequent work has concerned the development of parallel algorithms, the probabilistic analysis of combinatorial optimization problems,and the construction of randomized algorithms for combinatorial problems. His current research is concerned with strategies for sequencing the human genome. Karp has received the U.S. National Medal of Science,Turing Award (ACM), the Fulkerson Prize(AMS and Math. Programming Society), the von Neumann Theory Prize(ORSA-TIMS), the Lanchester Prize (ORSA) the von Neumann Lectureship (SIAM) and the Distinguished Teaching Award (Berkeley). He is a member of the National Academy of Sciences and the National Academy of Engineering, and holds four honorary degrees.