

Richard M. Karp
Professor
Research Areas
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 thirtysix 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.
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. 10461058, 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. 19741979, 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. 113941139, 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. 120, 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. 104113.
 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. 5155, March 2003.
 E. P. Xing, M. Jordan, and R. M. Karp, "Feature selection for highdimensional 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. 601608.
 E. P. Xing and R. M. Karp, "CLIFF: Clustering of highdimensional microarray data via iterative feature filtering using normalized cuts," Bioinformatics, vol. 17, no. 90001, pp. S306S315, 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. RANDOMAPPROX '99, D. Hochbaum, K. Jansen, J. D. P. Rolim, and A. Sinclair, Eds., Lecture Notes in Computer Science, Vol. 1671, Berlin, Germany: SpringerVerlag, 1999, pp. 221232.
 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. 278285.
 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. 112.
 R. M. Karp and V. Ramachandran, "A Survey of Parallel Algorithms for SharedMemory Machines," University of California, Berkeley, Department of EECS, Tech. Rep. UCB/CSD88408, March 1988.
 R. M. Karp and M. O. Rabin, "Efficient randomized patternmatching algorithms," IBM J. Research and Development, vol. 31, no. 2, pp. 249260, March 1987.
 R. M. Karp, "Turing Award Lecture: Combinatorics, complexity and randomness," Communications of the ACM, vol. 29, no. 2, pp. 98109, 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. 302309.
 R. M. Karp, Ed., Complexity of Computation, SIAMAMS 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. 225231, 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. 85103.
 J. Edmonds and R. M. Karp, "Theoretical improvements in algorithmic efficiency for network flow problems," J. ACM, vol. 19, no. 2, pp. 248264, April 1972.
 M. Held and R. M. Karp, "The travelingsalesman problem and minimum spanning trees: Part II," Mathematical Programming, vol. 1, no. 1, pp. 625, Dec. 1971.



