IST Advisory Board Member
Richard Karp

Richard M. Karp was educated at the Boston Latin School and Harvard University, where he received a Ph.D. in Applied Mathematics in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department at the IBM Thomas J. Watson Research Center. From 1968 to 1994 he was a Professor of Computer Science, Mathematics and Operations Research at the University of California, Berkeley. From 1988 to 1995 he was associated with the International Computer Science Institute in Berkeley. In 1995 he became a Professor of Computer Science and Engineering and an Adjunct Professor of Molecular Biotechnology at the University of Washington. He rejoined the International Computer Science Institute in Berkeley in 1999 and is presently Professor in the Graduate School at UC Berkeley.

The unifying theme in Karp's work has been the study of combinatorial algorithms. His most significant work is the 1972 paper, "Reducibility Among Combinatorial Problems," which shows that many of the most commonly studied combinatorial problems are disguised versions of a single underlying problem, and thus are all of essentially the same computational complexity. 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, the physical mapping of large DNA molecules, the analysis of gene expression data, and other combinatorial problems arising in molecular biology.

Karp has received the U.S. National Medal of Science, the 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, the National Academy of Engineering and the American Philosophical Society. He is also a Fellow of the American Academy of Arts and Sciences. He holds four honorary degrees.