Richard M. Karp
Professor EmeritusInfo Links
Research Areas
Biosystems & Computational Biology (BIO)Operating Systems & Networking (OSNT)
Theory (THY)
Research Centers
Simons Institute for the Theory of Computing (SITC)Center for Computational Biology (CCB)
Industrial Engineering and Operations Research (IEOR)
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, Harvard1956, 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, 2011Society 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
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