|
2008 Kyoto Prize Laureates
Advanced Technology Category
Prize Field: Information Science
Richard Manning Karp
Computer Scientist
Affiliation: University of California, Berkeley; Senior Research Scientist, International Computer Science Institute
Title: University Professor
Date of Birth: January 3, 1935
Nationality: U.S.A.
Background: Dr. Karp has made fundamental contributions to the theory of computational complexity, which he began developing in the early 1970s by establishing the theory of NP-completeness. In addition to creating many practical computer algorithms of his own, Dr. Karp's work has exerted profound influence on the guiding principles behind the analysis and design of algorithms used in many scientific disciplines.
| 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 |
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. |
|
|
