Founding Director, Simons Institute for the Theory of Computing
Ph.D., Harvard University

E-mail: karp (at)                 


  • Theoretical Computer Science
  • Algorithms


  • 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 Problemsin 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.