The 2008 Laureates / Advanced Technology Category / Information Science
image

Richard Manning Karp

U.S.A. / January 3, 1935
Computer Scientist
University Professor, University of California, Berkeley ; Senior Research Scientist, International Computer Science Institute

"Fundamental Contributions to the Development of the Theory of Computational Complexity "
Dr. Karp has made fundamental contributions to the development of the theory of computational complexity which began in the early 1970s by establishing the theory of NP-completeness, having a profound influence on the guiding principles for analysis and design of algorithms. He has also developed many practically relevant computer algorithms.

BRIEF BIOGRAPHY
1935
Born in Boston, Massachusetts, U.S.A.
1959
Ph.D. (Applied Mathematics), Harvard University
1959-1968
Research Staff Member, IBM Thomas J. Watson Research Center
1968-1994
Professor, University of California, Berkeley
1988-1995
Research Scientist, International Computer Science Institute
1995-1999
Professor, University of Washington
1999-present
University Professor, University of California, Berkeley
Senior Research Scientist, International Computer Science Institute

SELECTED AWARDS AND HONORS
1979
Delbert Ray Fulkerson Prize in Discrete Mathematics, Mathematical Programming Society and American Mathematical Society
1985
A.M.Turing Award, Association for Computing Machinery
1986
Distinguished Teaching Award, University of California, Berkeley
1996
National Medal of Science
1998
Harvey Prize, The Technion-Israel Institute of Technology
2004
Benjamin Franklin Medal, The Franklin Institute
Member:
National Academy of Sciences, National Academy of Engineering, American Academy of Arts and Sciences, American Association for the Advancement of Science, American Philosophical Society

SELECTED PUBLICATIONS
1971
The traveling-salesman problem and minimum spanning trees: Part II (Held, M. and Karp, R.). Mathematical Programming 1: 6-25.
1972
Reducibility among Combinatorial Problems (Miller, R. E. and Thatcher, J. W. eds.). in Proceedings of Complexity of Computer Computations, Plenum Press, New York, 85-103.
1972
Theoretical improvements in algorithmic efficiency for network flow problems (Edmonds, J. and Karp, R.). Journal of the ACM 19: 248-264.
1979
Random walks, universal traversal sequences, and the complexity of maze problems (Aleliunas, R., Karp, R. M., Lipton, R., Lovász, L. and Rackoff, C.). 20th Annual Symposium on Foundations of Computer Science : 218-223.
1985
A fast parallel algorithm for the maximal independent set problem (with Wigderson, A.). Journal of the ACM 32: 762-773.
2003
Conserved pathways within bacteria and yeast as revealed by global protein network alignment (Kelley, B. P., Sharan, R., Karp, R. M., Sittler, T., Root, D. E., Stockwell, B. R.,and Ideker, T). Proceedings of the National Academy of Sciences 100: 11394-11399.