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

• 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

• 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.

Technical Reports

• 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.