# Faculty Publications - Richard M. Karp

## 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

- 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. [abstract] - M. Zaharia, W. J. Bolosky, K. Curtis, A. Fox, D. A. Patterson, S. Shenker, I. Stoica, R. M. Karp, and T. Sittler, "Faster and More Accurate Sequence Alignment with SNAP,"
*CoRR*, vol. abs/1111.5572, 2011. - 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. - D. E. Culler, R. M. Karp, D. A. Patterson, A. Sahay, E. Santos, K. Schauser, R. Subramonian, and T. von Eicken, "LogP: A Practical Model of Parallel Computation,"
*Communications of the ACM*, vol. 39, no. 11, pp. 78-85, Nov. 1996. - L. Hellerstein, G. Gibson, R. M. Karp, R. H. Katz, and D. A. Patterson, "Coding techniques for handling failures in large disk arrays,"
*Algorithmica*, vol. 12, no. 2-3, Aug. 1994. [abstract] - 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. - G. Gibson, L. Hellerstein, R. M. Karp, R. H. Katz, and D. A. Patterson, "Failure Correction Techniques for Large Disk Arrays," in
*Proceedings of the third international conference on Architectural support for programming languages and operating systems*, ACM SIGARCH Computer Architecture News, Vol. 17, New York, NY: ACm, 1989, pp. 123-132. [abstract] - 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.

## Technical Reports

- L. Hodgkinson and R. M. Karp, "Algorithms to detect multi-protein modularity conserved during evolution," EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2011-7, Jan. 2011. [abstract]
- C. Daskalakis, G. A. Dimakis, R. M. Karp, and M. Wainwright, "Probabilistic Analysis of Linear Programming Decoding," UC Berkeley, Department of Statistics, Tech. Rep. UCB/STAT-06-718, Oct. 2006.
- P. B. Godfrey and R. M. Karp, "On the Price of Heterogeneity in Parallel Systems," EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2006-81, May 2006. [abstract]
- E. P. Xing and R. M. Karp, "LOGOS: A Hierarchical Bayesian Markovian Motif Model Capturing Local Site-Dependencies and Global Motif Distributions," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-03-1225, Jan. 2003. [abstract]
- E. Eskin, E. Halperin, and R. M. Karp, "Efficient Reconstruction of Haplotype Structure via Perfect Phylogeny," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-02-1196, Aug. 2002. [abstract]
- D. E. Culler, R. Karp, D. A. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, and T. von Eicken, "LogP: Towards a Realistic Model of Parallel Computation," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-92-713, Dec. 1992. [abstract]
- R. Karp, A. Sahay, and E. Santos, "Optimal Broadcast and Summation in the LogP Model," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-92-721, Nov. 1992. [abstract]
- R. M. Karp, U. Vazirani, and V. Vazirani, "An Optimal Algorithm for On-Line Bipartite Matching," EECS Department, University of California, Berkeley, Tech. Rep. UCB/ERL M91/18, 1991.
- G. A. Gibson, L. Hellerstein, R. M. Karp, R. H. Katz, and D. A. Patterson, "Coding Techniques for Handling Failures in Large Disk Arrays," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-88-477, Dec. 1988. [abstract]
- 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 V. Ramachandran, "A Survey of Parallel Algorithms for Shared-Memory Machines," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-88-408, March 1988. [abstract]
- R. M. Karp, R. Motwani, and N. Nisan, "Probabilistic Analysis of Network Flow Algorithms," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-88-392, Dec. 1987. [abstract]
- P. B. Gibbons, R. M. Karp, G. L. Miller, and D. Soroker, "Subtree Isomorphism is in Random NC," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-87-389, Dec. 1987. [abstract]
- R. M. Karp, R. Motwani, and P. Raghavan, "Deferred Data Structuring," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-87-320, Dec. 1986. [abstract]
- R. M. Karp, E. Upfat, and A. Wigderson, "The Complexity of Parallel Search," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-87-310, Oct. 1986. [abstract]
- N. Karmarker and R. M. Karp, "The Differencing Method of Set Partitioning," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-83-113, 1983. [abstract]
- I. Adler, R. Karp, and R. Shamir, "A Simplex Variant Solving An m x d Linear Program in O(min(m squared, d squared)) Expected Number of Pivot Steps," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-83-158, Dec. 1983. [abstract]
- I. Adler, R. Karp, and R. Shamir, "A Family of Simplex Variants Solving An m x d Linear Program in Expected Number of Pivot Steps Depending on d Only," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-83-157, Dec. 1983. [abstract]
- R. M. Karp and M. G. Luby, "A New Monte-Carlo Method for Estimating the Failure Probability of an n-Component System," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-83-117, Feb. 1983. [abstract]

## Patents

- M. A. Shokrollahi, S. Lassen, and R. Karp, "Systems and processes for decoding a chain reaction code through inactivation," U.S. Patent 7,030,785. April 2006.
- M. A. Shokrollahi, S. Lassen, and R. Karp, "Systems and processes for decoding a chain reaction code through inactivation," U.S. Patent Application. Feb. 2006.
- M. A. Shokrollahi, S. Lassen, and R. Karp, "Systems and processes for decoding chain reaction codes through inactivation," U.S. Patent 6,856,263. Feb. 2005.
- R. Stoughton and R. M. Karp, "Methods for testing biological network models," U.S. Patent 6,132,969. Nov. 2000.
- R. M. Karp, "Multiconnection switching networks," U.S. Patent 5,469,154. Nov. 1995.
- L. P. Horwitz and R. M. Karp, "Translator," U.S. Patent 3,354,296. Nov. 1967.
- L. P. Horwitz and R. M. Karp, "Optimum result computer," U.S. Patent 3,339,182. Aug. 1967.

## Talks or presentations

- R. M. Karp, "Computer Science as a Lens on the Sciences (Keynote Address)," presented at 28th International Conference on Distributed Computing Systems, Beijing, China, June 2008. [abstract]
- R. M. Karp, "Computer Science as a Lens on the Sciences: The Example of Computational Molecular Biology (Joint Keynote Address)," in
*Proc. 2007 IEEE Intl. Conf. on Bioinformatics and Biomedicine (BIBM.2007)*, X. Hu, I. Mandoiu, Z. Obradovic, and J. Xia, Eds., presented at 2007 IEEE Intl. Conf. on Bioinformatics and Biomedicine (BIBM 2007), Fremont, CA, Nov. 2007. - R. M. Karp, "Keynote Address: Algorithms for Inferring Cis-Regulatory Structures and Protein Interaction Networks," in
*Proc. 8th Annual Intl. Conf. on Research in Computational and Molecular Biology (RECOMB '04)*, presented at 8th Annual Intl. Conf. on Research in Computational and Molecular Biology (RECOMB '04), San Diego, CA, March 2004. - R. M. Karp, "Keynote Address: The Role of Algorithmic Research in Computational Genomics," presented at Proc. 2nd Intl. IEEE Computer Society Computational Systems Bioinformatics Conf. (CSB 2003), Stanford, CA, Aug. 2003.
- R. M. Karp, "Award Talk: The Genomics Revolution and Its Challenges for Algorithmic Research," presented at 27th Intl. Colloquium on Automata, Languages and Programming (ICALP 2000), Geneva, Switzerland, July 2000.