Richard Karp

Richard Karp is a University Professor at the University of California, Berkeley, in the Department of Electrical Engineering and Computer Sciences with joint appointments in Mathematics and Bioengineering. He earned his A.B. in Mathematics in 1955, S.M. in Applied Mathematics in 1956, and Ph.D. in Applied Mathematics in 1959, all from Harvard University. Following his doctorate, Karp joined the Mathematical Sciences Department at IBM Research from 1959 to 1968. In 1968, he became a professor at UC Berkeley in Computer Science and Industrial Engineering and Operations Research, holding the Class of 1939 Chair until 1994. From 1995 to 1999, he served as a professor at the University of Washington. He returned to UC Berkeley in 1999 as University Professor. Additionally, he has been a Research Scientist at the International Computer Science Institute in Berkeley from 1988 to 1995 and since 1999, and he was the founding Director of the Simons Institute for the Theory of Computing from 2012 to 2017. Karp has supervised thirty-six Ph.D. dissertations throughout his career.

Karp's research centers on combinatorial algorithms, with pioneering contributions to the theory of computational complexity. His seminal 1972 paper, 'Reducibility Among Combinatorial Problems,' demonstrated that twenty-one well-known combinatorial problems are NP-complete, establishing a foundational methodology for identifying computationally intractable problems that has influenced thousands of subsequent studies. Other key works include efficient algorithms for network flow and bipartite matching, the LogP model of parallel computation (1993), a simple algorithm for finding frequent elements in streams (2003, with Shenker and Papadimitriou), and recent publications on multiprotein modularity in evolution (2012). His current interests focus on algorithmic methods in genomics and computer networking. Karp has received the Turing Award (1985) for contributions to algorithm theory and NP-completeness, the U.S. National Medal of Science (1996), Kyoto Prize (2008), Harvey Prize, Fulkerson Prize (1979), Von Neumann Theory Prize (1990), Lanchester Prize, Babbage Prize, and eight honorary degrees. He is a member of the U.S. National Academies of Sciences and Engineering, the American Philosophical Society, the French Academy of Sciences, and a fellow of the American Academy of Arts and Sciences, AAAS, ACM, and INFORMS.

Professional Email: karp@cs.berkeley.edu