| 1 | Name: | Dr. Richard M. Karp | |
| Institution: | University of California, Berkeley | ||
| Year Elected: | 1994 | ||
| Class: | 1. Mathematical and Physical Sciences | ||
| Subdivision: | 104. Mathematics | ||
| Residency: | Resident | ||
| Living? : | Living | ||
| Birth Date: | 1935 | ||
Richard M. Karp was born in Boston, Massachusetts on January 3, 1935. He attended Boston Latin School and Harvard University, receiving his Ph.D. in 1959. From 1959-68 he was a member of the Mathematical Sciences Department at IBM Research. From 1968-94 and from 1999 to the present he has been a Professor at the University of California, Berkeley, where he held the Class of 1939 Chair and is currently a University Professor. From 1988-95 and 1999 to the present he has been a Research Scientist at the International Computer Science Institute in Berkeley. From 1995-99 he was a Professor at the University of Washington. During the 1985-86 academic year he was the co-organizer of a Computational Complexity Year at the Mathematical Sciences Research Institute in Berkeley. During the 1999-2000 academic year he was the Hewlett-Packard Visiting Professor at the Mathematical Sciences Research Institute. The unifying theme in Karp's work has been the study of combinatorial algorithms. His 1972 paper, "Reducibility Among Combinatorial Problems," showed that many of the most commonly studied combinatorial problems are NP-complete, and hence likely to be intractable. Much of his work has concerned parallel algorithms, the probabilistic analysis of combinatorial optimization algorithms and the construction of randomized algorithms for combinatorial problems. His current activities center around algorithmic methods in genomics and computer networking. He has supervised thirty-six Ph.D. dissertations. His honors and awards include the U.S. National Medal of Science, the Turing Award, the Kyoto Prize, the Fulkerson Prize, the Harvey Prize (Technion), Harvard University's Centennial Medal, the Lanchester Prize, the Von Neumann Theory Prize and Lectureship, the University of California, Berkeley's Distinguished Teaching Award and Miller Research Professorship, the Babbage Prize, and ten honorary degrees. He is a member of the U.S. National Academies of Sciences and Engineering, the American Philosophical Society and the French Academy of Sciences, and a Fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science, the Association for Computing Machinery and the Institute for Operations Research and Management Science. | |||