Richard M. Karp

Professor of Electrical Engineering and Computer Sciences

University of California, Berkeley

Summary

Richard Manning Karp (born January 3, 1935) is a computer scientist and computational theorist at the University of California, Berkeley, notable for research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008. Born to Abraham and Rose Karp in Boston, Massachusetts, Karp has three younger siblings: Robert, David, and Carolyn. He attended Harvard University, where he received his Bachelor's degree in 1955, his Master's degree in 1956, and his Ph.D. in applied mathematics in 1959. He started working at IBM's Thomas J. Watson Research Center. In 1968, he became Professor of Computer Science, Mathematics, and Operations Research at the University of California, Berkeley. Apart from a 4-year period as a professor at the University of Washington, he has remained at Berkeley. From 1988 to 1995 and 1999 to the present he has also been a Research Scientist at the International Computer Science Institute in Berkeley, where he currently leads the Algorithms Group. Richard Karp was awarded the National Medal of Science, and was the recipient of the Harvey Prize of the Technion and the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for his insights into computational complexity. In 1994 he was inducted as a Fellow of the Association for Computing Machinery. He is the recipient of several honorary degrees.

Richard Manning Karp (born January 3, 1935) is a computer scientist and computational theorist at the University of California, Berkeley, notable for research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008. Born to Abraham and Rose Karp in Boston, Massachusetts, Karp has three younger siblings: Robert, David, and Carolyn. He attended Harvard University, where he received his Bachelor's degree in 1955, his Master's degree in 1956, and his Ph.D. in applied mathematics in 1959. He started working at IBM's Thomas J. Watson Research Center. In 1968, he became Professor of Computer Science, Mathematics, and Operations Research at the University of California, Berkeley. Apart from a 4-year period as a professor at the University of Washington, he has remained at Berkeley. From 1988 to 1995 and 1999 to the present he has also been a Research Scientist at the International Computer Science Institute in Berkeley, where he currently leads the Algorithms Group. Richard Karp was awarded the National Medal of Science, and was the recipient of the Harvey Prize of the Technion and the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for his insights into computational complexity. In 1994 he was inducted as a Fellow of the Association for Computing Machinery. He is the recipient of several honorary degrees.

Current Institution | University of California, Berkeley |

Current School | Collage of Engineering |

Department | Electrical Engineering and Computer Sciences |

Disciplines | Physical Sciences: Computer SciencePhysical Sciences: Engineering: Electrical Engineering |

Geographical Focus | Americas |

Current and Past Advisor(s) | Anthony Oettinger |

Birthday | January 3,1935 |

Address | 621 Soda Hall #1776 Berkeley California 94720-1776 United States Phone: 510-642-5799 |

Office Hours | M 1:30-2:30 |

Profile viewed 1281 times

Publication Summary

**Publications**

**Books**

- R. M. Karp, Ed., Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, Providence, RI: American Mathematical Society, 1974.

**Book Chapters or Sections**

- I. Ulitsky, R. M. Karp, and R. Shamir, "Detecting disease-specific dysregulated pathways via analysis of clinical expression profiles," in Research in Computational Molecular Biology: Proc. 12th Annual Intl. Conf. (RECOMB 2008), M. Vingron and L. Wong, Eds., Lecture Notes in Computer Science::Lecture Notes in Bioinformatics, Vol. 4955, Berlin, Germany: Springer-Verlag, 2008, pp. 347-359.
- R. M. Karp, "Streaming algorithms for selection and approximate sorting," in Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2007) : Proc. 27th Intl. Conf., V. Arvind and S. Prasad, Eds., Lecture Notes in Computer Science, Vol. 4855, Berlin, Germany: Springer-Verlag, 2007, pp. 9-20.
- R. M. Karp, T. Nierhoff, and T. Tantau, "Optimal flow distribution among multiple channels with unknown capacities," in Theoretical Computer Science: Essays in Memory of Shimon Even, O. Goldreich, A. L. Rosenberg, and A. L. Selman, Eds., Lecture Notes in Computer Science, Vol. 3895, Berlin, Germany: Springer-Verlag, 2006, pp. 111-128.
- R. M. Karp, "Fair bandwidth allocation without per-flow state," in Theoretical Computer Science: Essays in Memory of Shimon Even, O. Goldreich, A. L. Rosenberg, and A. L. Selman, Eds., Lecture Notes in Computer Science, Vol. 3895, Berlin, Germany: Springer-Verlag, 2006, pp. 88-110.
- J. Scott, T. Ideker, R. M. Karp, and R. Sharaan, "Efficient algorithms for detecting signaling pathways in protein interaction networks," in Research in Computational Molecular Biology: Proc. 9th Annual Intl. Conf. (RECOMB '05), S. Miyano, J. Sesirov, S. Kasif, S. Istrail, P. Pevzner, and M. Waterman, Eds., Lecture Notes in Bioinformatics, Vol. 3500, Berlin, Germany: Springer-Verlag, 2005, pp. 1-13.
- M. Narayanan and R. M. Karp, "Gapped local similarity search with provable guarantees," in Algorithms in Bioinformatics: Proc. 4th Intl. Workshop (WABI 2004), I. Jonassen and J. Kim, Eds., Lecture Notes in Bioinformatics, Vol. 3240, Berlin, Germany: Springer-Verlag, 2004, pp. 74-86.
- E. Halperin and R. M. Karp, "The minimum-entropy set cover problem," in Automata, Languages and Programming: Proc. 31st Intl. Colloquium (ICALP 2004), J. Diaz, J. Karhumaki, A. Lepisto, and D. Sannella, Eds., Vol. 3142, Berlin, Germany: Springer-Verlag, 2004, pp. 733-744.
- R. M. Karp, "The role of experimental algorithms in genomics," in Experimental and Efficient Algorithms: Proc. 3rd Intl. Workshop (WEA 2004), C. C. Ribeiro and S. L. Martins, Eds., Lecture Notes in Computer Science, Vol. 3059, Berlin, Germany: Springer-Verlag, 2004, pp. 299-300.
- J. Elson, R. M. Karp, C. Papadimitriou, and S. Shenker, "Global synchronization in sensornets," in LATIN 2004: Theoretical Informatics--Proc. 6th Latin American Symp., M. Farach-Colton, Ed., Lecture Notes in Computer Science, Vol. 2976, Berlin, Germany: Springer-Verlag, 2004, pp. 609-624.
- E. P. Xing, M. Jordan, R. M. Karp, and S. J. Russell, "A hierarchical Bayesian Markovian model for motifs in biopolymer sequences," in Proc. 16th Annual Advances in Neural Information Processing Systems (NIPS 2002), S. Becker, S. Thrun, and K. Obermayer, Eds., Bradford Books, Vol. 15, Cambridge, MA: MIT Press, 2003, pp. 1513-1520.
- R. M. Karp and C. Kenyon, "A gambling game arising in the analysis of adaptive randomized rounding," in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: Proc. 2003 RANDOM-APPROX Workshops, S. Arora, K. Jansen, J. D. P. Rolim, and A. Sahai, Eds., Lecture Notes in Computer Science, Vol. 2764, Berlin, Germany: Springer-Verlag, 2003, pp. 1081-1099.
- A. Rao, K. Lakshminarayanan, S. Surana, R. M. Karp, and I. Stoica, "Load balancing in structured P2P systems," in Peer-to-Peers Systems II: 2nd Intl. Workshop (IPTPS '03). Revised Papers, F. Kaashoek and I. Stoica, Eds., Lecture Notes in Computer Science, Vol. 2735, Berlin, Germany: Springer-Verlag, 2003, pp. 68-79.
- J. Edmonds and R. M. Karp, "Theoretical improvements in algorithmic efficiency for network flow problems," in Combinatorial Optimization -- Eureka, You Shrink!: Papers dedicated to Jack Edmonds. 5th Intl. Workshop. Revised Papers, M. Junger, G. Reinelt, and G. Rinaldi, Eds., Lecture Notes in Computer Science, Vol. 2570, Berlin, Germany: Springer-Verlag, 2003, pp. 31-33.
- S. Ratnasamy, M. Handley, R. M. Karp, and S. Shenker, "Application-level multicast using content-addressable networks," in Networked Group Communication: Proc. 3rd Intl. COST264 Workshop (NGC 2001), J. Crowcroft and M. Hofmann, Eds., Lecture Notes in Computer Science, Vol. 2233, Berlin, Germany: Springer-Verlag, 2001, pp. 14-29.
- R. M. Karp, "The genomics revolution and its challenges for algorithmic research," in Current Trends in Theoretical Computer Science: Entering the 21st Century, G. Paun, G. Rozenberg, and A. Salomaa, Eds., River Edge, NJ: World Scientific Publishing Co., Inc., 2001, pp. 631-642. [abstract]
- 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 and V. Ramachandran, "Parallel algorithms for shared-memory machines," in Handbook of Theoretical Computer Science (Vol. A): Algorithms and Complexity, J. van Leeuwen, Ed., New York, NY: Elsevier, 1991, pp. 869-941.
- 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.

**Articles in Journals or Magazines**

- G. Kimmel, R. M. Karp, M. Jordan, and E. Halperin, "Association mapping and significance estimation via the coalescent," American J. Human Genetics, vol. 83, no. 6, pp. 675-683, Nov. 2008.
- C. Daskalakis, A. G. Dimakis, R. M. Karp, and M. Wainwright, "Probabilistic analysis of linear programming decoding," IEEE Trans. Information Theory, vol. 54, no. 8, pp. 3565-3578, Aug. 2008.
- R. B. Godfrey and R. M. Karp, "On the price of heterogeneity in parallel systems," Theory of Computing Systems, pp. online, Jan. 2008.
- R. M. Karp, M. Li, P. Pevzner, and R. Shamir, "Foreword: Special Issue on Computational Molecular Biology," J. Computer and System Sciences: Bioinformatics III, vol. 73, no. 7, pp. 1023-1023, Nov. 2007.
- G. Kimmel, M. Jordan, E. Halperin, R. Shamir, and R. M. Karp, "A randomization test for controlling population stratification in whole-genome association studies," American J. Human Genetics, vol. 81, no. 5, pp. 895-905, Nov. 2007.
- R. M. Karp, M. Li, P. Pevzner, and R. Shamir, "Foreword: Special Issue on Computational Molecular Biology," J. Computer and Systems Sciences: Bioinformatics III, vol. 73, no. 7, pp. 1023-1023, Nov. 2007.
- B. Kirkpatrick, C. S. Armendariz, R. M. Karp, and E. Halperin, "HAPLOPOOL: Improving haplotype frequency estimation through DNA pools and phylogenetic modeling," Bioinformatics, vol. 23, no. 22, pp. 3048-3055, Nov. 2007.
- I. Gat-Viks, R. M. Karp, R. Shamir, and R. Sharan, "Reconstructing chain functions in genetic networks," SIAM J. Discrete Mathematics, vol. 20, no. 3, pp. 727-740, Aug. 2006.
- J. Scott, T. Ideker, R. M. Karp, and R. Sharan, "Efficient algorithms for detecting signaling pathways in protein interaction networks," J. Computational Biology: Special RECOMB 2005 Issue, vol. 13, no. 2, pp. 133-144, March 2006.
- S. Surana, B. Godfrey, K. Lakshminarayanan, R. M. Karp, and I. Stoica, "Load balancing in dynamic structured peer-to-peer systems," Performance Evaluation, vol. 63, no. 3, pp. 217-240, March 2006.
- E. Halperin and R. M. Karp, "The minimum-entropy set cover problem," Theoretical Computer Science: Automata, Languages and Programming: Algorithms and Complexity, vol. 348, no. 2-3, pp. 240-250, Dec. 2005.
- I. Adler, H. Ahn, R. M. Karp, and S. M. Ross, "A probabilistic model for survivability of cells," J. Applied Probability, vol. 42, no. 4, pp. 919-931, Dec. 2005.
- R. Sharan, T. Ideker, B. Kelley, R. Shamir, and R. M. Karp, "Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data," J. Computational Biology, vol. 12, no. 6, pp. 835-846, July 2005.
- R. M. Karp, M. Li, P. Pevzner, and R. Shamir, "Guest Editors' Foreword: Special Issue on Computational Molecular Biology," J. Computer and Systems Science: Special Issue on Bioinformatics II, vol. 70, no. 3, pp. 283-283, May 2005.
- 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.
- A. Ben-Dor, T. Hartman, R. M. Karp, B. Schwikowski, R. Sharan, and Z. Yakhini, "Towards optimally multiplexed applications of universal arrays," J. Computational Biology, vol. 11, no. 2-3, pp. 477-493, March 2004.
- E. P. King, W. Wu, M. Jordan, and R. M. Karp, "LOGOS: A modular Bayesian model for de novo motif detection," J. Bioinformatics and Computational Biology, vol. 2, no. 1, pp. 127-154, March 2004.
- I. Adler, H. Ahn, R. M. Karp, and S. M. Ross, "Coalescing times for IID random variables with applications to population biology," Random Structures & Algorithms, vol. 23, no. 2, pp. 155-166, Sep. 2003.
- 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.
- R. Sharan, I. Ovcharenko, A. Ben-Hur, and R. M. Karp, "CREME: A framework for identifying cis-regulatory modules in human-mouse conserved segments," Bioinformatics: Proc. of the 11th Intl. Conf. on Intelligent Systems for Molecular Bio, vol. 19, no. Supp. 1, pp. i283-i291, July 2003.
- E. Halperin, J. Buhler, R. M. Karp, R. Krauthgamer, and B. Westover, "Detecting protein sequence conservation via metric embeddings," Bioinformatics, vol. 19, no. Supp. 1, pp. i122-i129, July 2003.
- A. Ben-Dor, R. M. Karp, B. Schwikowski, and R. Shamir, "The restriction scaffold problem," J. Computational Biology, vol. 10, no. 3-4, pp. 385-398, June 2003.
- A. Ben-Dor, B. Chor, R. M. Karp, and Z. Yakhini, "Discovering local structure in gene expression data: The order-preserving submatrix problem," J. Computational Biology, vol. 10, no. 3-4, pp. 373-384, June 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.
- 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.
- A. Akella, S. Seshan, R. M. Karp, S. Shenker, and C. Papadimitriou, "Selfish behavior and stability of the Internet: A game-theoretic analysis of TCP," ACM SIGCOMM Computer Communication Review: Proc. 2002 SIGCOMM Conf., vol. 32, no. 4, pp. 117-130, Oct. 2002.
- P. Beame, R. M. Karp, T. Pitassi, and M. Saks, "The efficiency of resolution and Davis-Putnam procedures," SIAM J. Computing, vol. 31, no. 4, pp. 1048-1075, April 2002.
- S. Ratnasamy, P. Francis, M. Handley, R. M. Karp, and S. Shenker, "A scalable content-addressable network," ACM SIGCOMM Computer Communication Review: Proc. 2001 SIGCOMM Conf., vol. 31, no. 4, pp. 161-172, Oct. 2001.
- 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.
- R. El-Yaniv, A. Fiat, R. M. Karp, and G. Turpin, "Optimal search and one-way trading online algorithms," Algorithmica, vol. 30, no. 1, pp. 101-139, May 2001.
- A. Condon and R. M. Karp, "Algorithms for graph partitioning on the planted partition model," Random Structures & Algorithms, vol. 18, no. 2, pp. 116-140, March 2001.
- M. Adler, J. W. Byers, and R. M. Karp, "Parallel sorting with limited bandwidth," SIAM J. Computing, vol. 29, no. 6, pp. 1997-2015, 2000.
- P. Dagum, R. M. Karp, M. Luby, and S. M. Ross, "An optimal algorithm for Monte Carlo estimation," SIAM J. Computing, vol. 29, no. 5, pp. 1484-1496, 2000.
- R. M. Karp, I. Pe'er, and R. Shamir, "An algorithm combining discrete and continuous methods for optical mapping," J. Computational Biology, vol. 7, no. 5, pp. 745-760, Oct. 2000.
- A. Ben-Dor, R. M. Karp, B. Schwikowski, and Z. Yakhini, "Universal DNA tag systems: A combinatorial design scheme," J. Computational Biology, vol. 7, no. 3-4, pp. 503-519, Aug. 2000.
- R. M. Karp, "Mathematical challenges from genomics and molecular biology," Notices of the American Mathematical Society, vol. 49, no. 5, pp. 544-553, May 2000.
- R. M. Karp and R. Shamir, "Algorithms for optical mapping," J. Computational Biology, vol. 7, no. 1/2, pp. 303-316, Feb. 2000.
- A. Condon, H. Edelsbrunner, E. A. Emerson, L. Fortnow, S. Haber, R. M. Karp, D. Leivant, R. Lipton, N. Lynch, I. Parberry, C. Papadimitriou, M. Rabin, A. Rosenberg, J. S. Royer, J. Savage, A. L. Selman, C. Smith, E. Tardos, and J. S. Vitter, "Challenges for theory of computing," ACM SIGACT News, vol. 30, no. 2, pp. 62-76, June 1999.
- A. V. Aho, D. S. Johnson, R. M. Karp, S. R. Kosaraju, C. C. McGeoch, C. Papadimitriou, and P. Pevzner, "Emerging opportunities for Theoretical Computer Science," ACM SIGACT News, vol. 28, no. 3, pp. 65-74, Sep. 1997.
- A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, and N. E. Young, "Competitive paging algorithms," J. Algorithms, vol. 12, no. 4, pp. 685-699, Dec. 1991.
- 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.
- 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.
- 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.
- M. Held and R. M. Karp, "The traveling-salesman problem and minimum spanning trees," Operations Research, vol. 18, no. 6, pp. 1138-1162, Nov. 1970.
- R. M. Karp and R. E. Miller, "Parallel program schemata," J. Computer and System Sciences, vol. 3, no. 2, pp. 147-195, May 1969.
- M. Held and R. M. Karp, "A dynamic programming approach to sequencing problems," J. Society for Industrial and Applied Mathematics, vol. 10, no. 1, pp. 196-210, March 1962.

**Articles in Conference Proceedings**

- L. Hodgkinson and R. M. Karp, "Algorithms to detect multiprotein modularity conserved during evolution," in Proceedings of the 7th International Symposium on Bioinformatics Research and Applications, LNCS/LNBI, Vol. 6674, Springer, 2011, pp. 111-122. [abstract]
- H. Lin, C. Amanatidis, M. Sideri, R. M. Karp, and C. Papadimitriou, "Linked decompositions of networks and the power of choice in Polya urns," in Proc. 19th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA '08), Philadelphia, PA: Society for Industrial and Applied Mathematics, 2008, pp. 993-1002.
- L. Popa, A. Rostamizadeh, R. M. Karp, C. Papadimitriou, and I. Stoica, "Balancing traffic load in wireless networks with curveball routing," in Proc. 8th ACM Intl. Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc '07), New York, NY: The Association for Computing Machinery, Inc., 2007, pp. 170-179.
- R. M. Karp and R. Kleinberg, "Noisy binary search and its applications," in Proc. 18th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2007), New York, NY/Philadelphia, PA: The Association for Computing Machinery, Inc./Society for Industrial and Applied Mathematics, 2007, pp. 881-890.
- K. Daskalakis, G. A. Dimakis, R. M. Karp, and M. Wainwright, "Probabilistic analysis of linear programming decoding," in Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New York, NY/Philadelphia, PA: The Association for Computing Machinery, Inc./Society for Industrial and Applied Mathematics, 2007, pp. 385-394.
- R. B. Godfrey and R. M. Karp, "On the price of heterogeneity in parallel systems," in Proc. 18th Annual ACM Symp. on Parallelism in Algorithms and Architectures (SPAA '06), New York, NY: The Association for Computing Machinery, Inc., 2006, pp. 84-92.
- R. M. Karp, M. Luby, and A. Shokrollahi, "Verification decoding of Raptor codes," in Proc. 2005 IEEE Intl. Symp. on Information Theory (ISIT 2005), Piscataway, NJ: IEEE Press, 2005, pp. 1310-1314.
- R. M. Karp, M. Luby, and A. Shokrollahi, "Finite length analysis of LT codes," in Proc. 2004 IEEE Intl. Symp. on Information Theory (ISIT 2004), Piscataway, NJ: IEEE Press, 2004, pp. 37-37.
- E. Halperin and R. M. Karp, "Perfect phylogeny and haplotype assignment," in Proc. 8th Annual Intl. Conf. on Research in Computational Molecular Biology (RECOMB '04), New York, NY: The Association for Computing Machinery, Inc., 2004, pp. 10-19.
- B. Godfrey, K. Lakshminarayanan, S. Surana, R. M. Karp, and I. Stoica, "Load balancing in dynamic structured P2P systems," in Proc. IEEE INFOCOM 2004, Vol. 4, Piscataway, NJ: IEEE Press, 2004, pp. 2253-2262.
- R. Sharan, T. Ideker, B. P. Kelley, R. Shamir, and R. M. Karp, "Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data," in Proc. 8th Annual Intl. Conf. on Research in Computational Molecular Biology (RECOMB '04), New York, NY: The Association for Computing Machinery, Inc., 2004, pp. 282-289.
- I. Gat-Viks, R. Shamir, R. M. Karp, and R. Sharan, "Reconstructing chain functions in genetic networks," in Proc. 9th Pacific Symp. on Biocomputing (PSB 2004), R. B. Altman, A. K. Dunker, L. Hunter, T. A. Jung, and T. E. Klein, Eds., Hackensack, NJ: World Scientific Publishing Co., Inc., 2004, pp. 498-509.
- E. P. Xing, W. Wu, M. Jordan, and R. M. Karp, "LOGOS: A modular Bayesian model for de novo motif detection," in Proc. 2nd Intl. IEEE Computer Society Computational Systems Bioinformatics Conf. (CSB 2003), Los Alamitos, CA: IEEE Computer Society, 2003, pp. 266-276.
- S. Ratnasamy, M. Handley, R. M. Karp, and S. Shenker, "Topologically-aware overlay construction and server selection," in Proc. 21st Annual Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2002), Vol. 3, Piscataway, NJ: IEEE Press, 2003, pp. 1190-1199.
- M. Adler, E. Halperin, R. M. Karp, and V. V. Vazirani, "A stochastic process on the hypercube with applications to peer-to-peer networks," in Proc. 35th Annual ACM Symp. on Theory of Computing (STOC 2003), New York, NY: The Association for Computing Machinery, Inc., 2003, pp. 575-584.
- 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.
- A. Akella, S. Seshan, R. M. Karp, S. Shenker, and C. Papadimitriou, "Selfish behavior and stability of the Internet: A game-theoretic analysis of TCP," in Proc. 2002 Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '02), New York, NY: The Association for Computing Machinery, Inc., 2002, pp. 117-130.
- A. Ben-Dor, R. M. Karp, B. Schwikowski, and R. Shamir, "The restriction scaffold problem," in Proc. 6th Annual Intl. Conf. on Research in Computational Molecular Biology (RECOMB '02), G. Myers, S. Hannenhalli, D. Sankoff, S. Istrail, P. Pevzner, and M. Waterman, Eds., New York, NY: The Association for Computing Machinery, Inc., 2002, pp. 58-66.
- A. Ben-Dor, B. Chor, R. M. Karp, and Z. Yakhini, "Discovering local structure in gene expression data: The order-preserving submatrix problem," in Proc. 6th Annual Intl. Conf. on Research in Computational Molecular Biology (RECOMB '02), G. Myers, S. Hannenhalli, D. Sankoff, S. Istrail, P. Pevzner, and M. Waterman, Eds., New York, NY: The Association for Computing Machinery, Inc., 2002, pp. 49-57.
- S. Ratnasamy, P. Francis, M. Handley, R. M. Karp, and S. Shenker, "A scalable content-addressable network," in Proc. ACM SIGCOMM 2001 Conf.: Applications, Technologies, Architectures, and Protocols for Computer Communications, New York, NY: The Association for Computing Machinery, Inc., 2001, pp. 161-172.
- 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.
- G. B. Horn and R. M. Karp, "A maximum likelihood polynomial time syndrome decoder to correct linearly independent errors," in Proc. 2001 IEEE Intl. Symp. on Information Theory (ISIT 2001), Piscataway, NJ: IEEE Press, 2001, pp. 87-87.
- R. M. Karp, E. Koutsoupias, C. Papadimitriou, and S. Shenker, "Optimization problems in congestion control," in Proc. 41st Annual Symp. on Foundations of Computer Science (FOCS 2000), Los Alamitos, CA: IEEE Computer Society, 2000, pp. 66-74.
- R. M. Karp, C. Schindelhauer, S. Shenker, and B. Vocking, "Randomized rumor spreading," in Proc. 41st Annual Symp. on Foundations of Computer Science (FOCS 2000), Los Alamitos, CA: IEEE Computer Society, 2000, pp. 565-574.
- A. Ben-Dor, R. M. Karp, B. Schwikowski, and Z. Yakhini, "Universal DNA tag systems: A combinatorial design scheme," in Proc. 4th Annual Conf. on Research in Computational Molecular Biology (RECOMB '00), R. Shamir, S. Miyano, S. Istrail, P. Pevzner, and M. Waterman, Eds., New York, NY: The Association for Computing Machinery, Inc., 2000, pp. 65-75.
- T. E. Ideker, V. Thorsson, and R. M. Karp, "Discovery of regulatory interactions through perturbation: Inference and experimental design," in Proc. 5th Pacific Symp. on Biocomputing (PSB 2000), R. B. Altman, A. K. Dunkere, L. Hunter, K. Lauderdale, and T. E. Klein, Eds., Hackensack, NJ: World Scientific Publishing Co., 1999, pp. 302-313.
- R. M. Karp, I. Pe'er, and R. Shamir, "An algorithm combining discrete and continuous methods for optical mapping," in Proc. 7th Intl. Conf. on Intelligent Systems for Molecular Biology (ISMB '99), T. Lengauer, R. Schneider, P. Bork, D. L. Brutlag, J. I. Glasgow, H. Mewes, and R. Zimmer, Eds., Menlo Park, CA: AAAI Press, 1999, pp. 159-168. [abstract]
- 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, U. Vazirani, and V. V. Vazirani, "An optimal algorithm for on-line bipartite matching," in Proc. 22nd Annual ACM Symp. on Theory of Computing, H. Ortiz, Ed., New York, NY: ACM Press, 1990, pp. 352-358.
- 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.

Books

Other Publications