Richard M. Karp
Biography
He attended Boston Latin School and Harvard University, receiving the Ph.D. in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department at IBM Research. From 1968 to 1994 and from 1999 to the present he has been a professor at UC Berkeley, where he held the Class of 1939 Chair. From 1988 to 1995 and 1999 to the present he has been a Research Scientist at the International Computer Science Institute in Berkeley.
His current activities center on algorithmic methods in genomics and computer networking. He has supervised thirty-six Ph.D. dissertations. Honors and awards include: U.S. National Medal of Science, Turing Award, Fulkerson Prize, Harvey Prize (Technion), Centennial Medal (Harvard), Lanchester Prize, Von Neumann Theory Prize, Von Neumann Lectureship, Distinguished Teaching Award (Berkeley), Faculty Research Lecturer (Berkeley), Miller Research Professor (Berkeley), Babbage Prize and eight honorary degrees. He is a member of the U.S. National Academies of Sciences and Engineering, the American Philosophical Society and the French Academy of Sciences, and a Fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science, the Association for Computing Machinery and the Institute for Operations Research and Management Science.
Education
- 1959, Ph.D., Applied Mathematics, Harvard
- 1956, S.M., Applied Mathematics, Harvard
- 1955, A.B., Mathematics, Harvard
Selected Publications
- L. Hodgkinson and R. M. Karp, "Algorithms to detect multiprotein modularity conserved during evolution," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 9, no. 4, pp. 1046-1058, July 2012.
- R. Sharan, S. Suthram, R. M. Kelley, T. Kuhn, S. McCuine, P. Uetz, T. Sittler, R. M. Karp, and T. Ideker, "Conserved patterns of protein interaction in multiple species," Proc. National Academy of Sciences of the United States of America, vol. 102, no. 6, pp. 1974-1979, Feb. 2005.
- B. P. Kelley, R. Sharan, R. M. Karp, T. Sittler, D. E. Root, B. R. Stockwell, and T. Ideker, "Conserved pathways within bacteria and yeast as revealed by global protein network alignment," Proc. National Academy of Sciences of the United States of America, vol. 100, no. 20, pp. 11394-1139, Sep. 2003.
- E. Eskin, E. Halperin, and R. M. Karp, "Efficient reconstruction of haplotype structure via perfect phylogeny," J. Bioinformatics and Computational Biology, vol. 1, no. 1, pp. 1-20, April 2003.
- E. Eskin, E. Halperin, and R. M. Karp, "Large scale reconstruction of haplotypes from genotype data," in Proc. 7th Annual Intl. Conf. on Research in Computational Molecular Biology, M. Vingron, S. Istrail, P. Pevzner, and M. Waterman, Eds., New York, NY: ACM Press, 2003, pp. 104-113.
- R. M. Karp, S. Shenker, and C. Papadimitriou, "A simple algorithm for finding frequent elements in streams and bags," ACM Trans. Database Systems, vol. 28, no. 1, pp. 51-55, March 2003.
- E. P. Xing, M. Jordan, and R. M. Karp, "Feature selection for high-dimensional genomic microarray data," in Proc. 18th Intl. Conf. on Machine Learning (ICML '01), C. E. Brodley and A. P. Danyluk, Eds., San Francisco, CA: Morgan Kaufmann Publishers Inc., 2001, pp. 601-608.
- E. P. Xing and R. M. Karp, "CLIFF: Clustering of high-dimensional microarray data via iterative feature filtering using normalized cuts," Bioinformatics, vol. 17, no. 90001, pp. S306-S315, June 2001.
- A. Condon and R. M. Karp, "Algorithms for graph partitioning on the planted partition model," in Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques: Proc. RANDOM-APPROX '99, D. Hochbaum, K. Jansen, J. D. P. Rolim, and A. Sinclair, Eds., Lecture Notes in Computer Science, Vol. 1671, Berlin, Germany: Springer-Verlag, 1999, pp. 221-232.
- R. M. Karp, "Mapping the genome: Some combinatorial problems arising in molecular biology," in Proc. 25th Annual ACM Symp. on Theory of Computing, New York, NY: ACM Press, 1993, pp. 278-285.
- D. E. Culler, R. M. Karp, D. A. Patterson, A. Sahay, K. E. Schauser, E. E. Santos, R. Subramonian, and T. von Eicken, "LogP: Towards a realistic model of parallel computation," in Proc. 4th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, New York, NY: ACM Press, 1993, pp. 1-12.
- R. M. Karp and V. Ramachandran, "A Survey of Parallel Algorithms for Shared-Memory Machines," University of California, Berkeley, Department of EECS, Tech. Rep. UCB/CSD-88-408, March 1988.
- R. M. Karp and M. O. Rabin, "Efficient randomized pattern-matching algorithms," IBM J. Research and Development, vol. 31, no. 2, pp. 249-260, March 1987.
- R. M. Karp, "Turing Award Lecture: Combinatorics, complexity and randomness," Communications of the ACM, vol. 29, no. 2, pp. 98-109, Feb. 1986.
- R. M. Karp and R. J. Lipton, "Some connections between nonuniform and uniform complexity classes," in Proc. 12th Annual ACM Symp. on Theory of Computing, New York, NY: ACM Press, 1980, pp. 302-309.
- R. M. Karp, Ed., Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, Providence, RI: American Mathematical Society, 1974.
- J. E. Hopcroft and R. M. Karp, "An $n^{5/2} $ algorithm for maximum matchings in bipartite graphs," SIAM J. Computing, vol. 2, no. 4, pp. 225-231, Dec. 1973.
- R. M. Karp, "Reducibility among combinatorial problems," in Complexity of Computer Computations: Proc. of a Symp. on the Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds., The IBM Research Symposia Series, New York, NY: Plenum Press, 1972, pp. 85-103.
- J. Edmonds and R. M. Karp, "Theoretical improvements in algorithmic efficiency for network flow problems," J. ACM, vol. 19, no. 2, pp. 248-264, April 1972.
- M. Held and R. M. Karp, "The traveling-salesman problem and minimum spanning trees: Part II," Mathematical Programming, vol. 1, no. 1, pp. 6-25, Dec. 1971.
Awards, Memberships and Fellowships
- ACM SIGCOMM Test of Time Paper Award, 2011
- Society for Industrial & Applied Mathematics (SIAM) Fellow, 2009
- Kyoto Prize, 2008
- IEEE CS TCDP Outstanding Contribution Award, 2008
- ACM SIGACT Distinguished Service Prize, 2008
- Benjamin Franklin Medal in Computer and Cognitive Science, 2004
- EATCS Award, 2000
- Harvey Prize, 1998
- Harvard Centennial Medal, 1997
- National Medal of Science, 1996
- CS Charles Babbage Award, 1995
- Association for Computing Machinery (ACM) Fellow, 1994
- National Academy of Engineering (NAE) Member, 1992
- INFORMS John von Neumann Theory Prize, 1990
- SIAM John von Neumann Lecture Prize, 1987
- UC Berkeley Distinguished Teaching Award, 1986
- ACM A.M. Turing Award, 1985
- American Academy of Arts and Sciences Member, 1980
- National Academy of Sciences (NAS) Member, 1980
- Delbert Ray Fulkerson Prize, 1979
- INFORMS Frederick W. Lanchester Prize, 1977
