Richard M. Karp
University of
Washington
(206) 543-4226
karp@cs.washington.edu
Awards and Memberships
National Medal of Science, 1996
Babbage Prize, 1995
UC Berkeley University Professor, 1994
ACM Fellow, 1994
ACM Turing Award, 1985
Member, National Academy of Sciences
Member, National Academy of Engineering
Fellow, American Academy of Arts and Sciences
Fellow, American Association for the Advancement of Science
Distinguished Teaching Award, UC Berkeley Academic Senate, 1986
Class of 1939 Chair, UC Berkeley
Lanchester Prize, Operations Research Society of America and Institute for Management Science, 1977
Fulkerson Prize, American Mathematical Society and Mathematical
Programming Society, 1979
John von Neumann Theory Prize, Operations Research Society of America and Institute for Management Science, 1990
Faculty Research Lecturer, UC Berkeley, 1981-1982
Hermann Weyl Lecturer, Institute for Advanced Study, 1979
John von Neumann Lecturer, Society for Industrial and Applied
Mathematics, 1987
Miller Research Professor, UC Berkeley, 1980-1981
Honorary Doctorates: Georgetown University, 1992; University of Massachusetts, 1990; Technion, 1989; University of Pennsylvania,
1986
Member, National Advisory Board, Computer Professionals for
Social Responsibility, 1989-present
Member, Board of Governors, Weizmann Institute of Science, 1989-present
Member, Board of Trustees, International Computer Science
Institute, 1988-present
Selected Publications
"Combinatorics, Complexity and Randomness" (Turing
Award Lecture), Communications of the ACM, Vol. 29
(1986), pp. 98-111.
"Constructing a Perfect Matching in Random NCS"
(with E. Upfal and A. Wigderson), Combinatorica, Vol. 6
(1986), pp. 35-48.
"Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane," Mathematics of
Operations Research, Vol. 2, No. 3 (1977), pp. 209-244.
"Theoretical Improvements in Algorithmic Efficiency for
Network Flow Problems" (with J. Edmonds), Journal of the
ACM, Vol. 18 (1972), pp. 264-284.
"Reducibility among Combinatorial Problems,"
in Complexity of Computer Computations, Plenum Press,
1972.
"The Traveling-Salesman Problem and Minimum Spanning
Trees: Part II" (with M. Held), Mathematical Programming,
Vol. 1 (1971), pp. 6-25.