Richard Karp

Professor

Ph.D., Harvard University

E-mail: karpcs.berkeley.edu

Research

  • Theoretical Computer Science
  • Algorithms

Awards/ Lectureships
  • 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, 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; Univ. 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
  • Chair, Computer Science Division, 1973-1975
Publications
  • Combinatorics, Complexity and Randomness
    (Turing Award Lecture), Communications 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), J. 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.