Electrical Engineering and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Cory-Soda Hall Logo

EE

CS


PeopleWebsite

Information for:

Students
Faculty
Staff

Support Services:

Administrative
Research
Computing
Facilities & Safety
My EECS Info

   

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

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.

Technical Reports

Patents

Talks or presentations