Richard M. Karp

According to our database, Richard M. Karp authored at least 207 papers between 1960 and 2019.

Collaborative distances:

• Dijkstra number of two.
• Erdős number of two.

2019

Massively Parallel Computation of Matching and MIS in Sparse Graphs.

Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, Jara Uitto

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018

Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching.

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Richard M. Karp

CoRR, 2018

2017

Random Knockout Tournaments.

Ilan Adler, Yang Cao, Richard M. Karp, Erol A. Peköz, Sheldon M. Ross

Oper. Res., 2017

2014

Finding a most biased coin with fewest flips.

Karthekeyan Chandrasekaran, Richard M. Karp

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Reconstructing Boolean Models of Signaling.

Roded Sharan, Richard M. Karp

J. Comput. Biol., 2013

The Implicit Hitting Set Approach to Solve Combinatorial Optimization Problems with an Application to Multigenome Alignment.

Erick Moreno-Centeno, Richard M. Karp

Oper. Res., 2013

2012

Algorithms to Detect Multiprotein Modularity Conserved during Evolution.

Luqman Hodgkinson, Richard M. Karp

IEEE ACM Trans. Comput. Biol. Bioinform., 2012

Comparing Pedigree Graphs.

Bonnie Kirkpatrick, Yakir Reshef, Hilary K. Finucane, Haitao Jiang, Binhai Zhu, Richard M. Karp

J. Comput. Biol., 2012

Theory of Computation as an Enabling Tool for the Sciences.

Richard M. Karp

Proceedings of the Theory and Applications of Models of Computation, 2012

Algorithmic methodologies for ultra-efficient inexact architectures for sustaining technology scaling.

Lingamneni Avinash, Kirthi Krishna Muntimadugu, Christian C. Enz, Richard M. Karp, Krishna V. Palem, Christian Piguet

Proceedings of the Computing Frontiers Conference, CF'12, 2012

An Algorithmic View of the Universe.

Christos H. Papadimitriou, Leonard M. Adleman, Richard M. Karp, Donald E. Knuth, Robert E. Tarjan, Leslie G. Valiant

Proceedings of the ACM Turing Centenary Celebration, 2012

2011

Sorting and Selection in Posets.

Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha J. Riesenfeld, Elad Verbin

SIAM J. Comput., 2011

Understanding Science Through the Computational Lens.

Richard M. Karp

J. Comput. Sci. Technol., 2011

Heuristic algorithms in computational molecular biology.

Richard M. Karp

J. Comput. Syst. Sci., 2011

Pedigree Reconstruction Using Identity by Descent.

Bonnie Kirkpatrick, Shuai Cheng Li, Richard M. Karp, Eran Halperin

J. Comput. Biol., 2011

Faster and More Accurate Sequence Alignment with SNAP

Matei Zaharia, William J. Bolosky, Kristal Curtis, Armando Fox, David A. Patterson, Scott Shenker, Ion Stoica, Richard M. Karp, Taylor Sittler

CoRR, 2011

Algorithms for Implicit Hitting Set Problems.

Karthekeyan Chandrasekaran, Richard M. Karp, Erick Moreno-Centeno, Santosh S. Vempala

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

Haplotype Inference in Complex Pedigrees.

Bonnie Kirkpatrick, Eran Halperin, Richard M. Karp

J. Comput. Biol., 2010

Topology-Free Querying of Protein Interaction Networks.

Sharon Bruckner, Falk Hüffner, Richard M. Karp, Ron Shamir, Roded Sharan

J. Comput. Biol., 2010

Algorithms for Comparing Pedigree Graphs

Bonnie Kirkpatrick, Yakir Reshef, Hilary K. Finucane, Haitao Jiang, Binhai Zhu, Richard M. Karp

CoRR, 2010

Prediction of Phenotype Information from Genotype Data.

Jens Gramm, Richard M. Karp, William S. Noble, Roded Sharan, Qianfei Wang, Nir Yosef

Commun. Inf. Syst., 2010

Implicit Hitting Set Problems and Multi-genome Alignment.

Richard M. Karp

Proceedings of the Combinatorial Pattern Matching, 21st Annual Symposium, 2010

Reducibility Among Combinatorial Problems.

Richard M. Karp

Proceedings of the 50 Years of Integer Programming 1958-2008, 2010

2009

Torque: topology-free querying of protein interaction networks.

Sharon Bruckner, Falk Hüffner, Richard M. Karp, Ron Shamir, Roded Sharan

Nucleic Acids Res., 2009

On the Price of Heterogeneity in Parallel Systems.

Brighten Godfrey, Richard M. Karp

Theory Comput. Syst., 2009

My memories of David Gale.

Richard M. Karp

Games Econ. Behav., 2009

Haplotype Inference in Complex Pedigrees.

Bonnie Kirkpatrick, Javier Rosa, Eran Halperin, Richard M. Karp

Proceedings of the Research in Computational Molecular Biology, 2009

2008

Probabilistic Analysis of Linear Programming Decoding.

Constantinos Daskalakis, Alexandros G. Dimakis, Richard M. Karp, Martin J. Wainwright

IEEE Trans. Inf. Theory, 2008

George Dantzig's impact on the theory of computation.

Richard M. Karp

Discret. Optim., 2008

Linked decompositions of networks and the power of choice in Polya urns.

Henry C. Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Detecting Disease-Specific Dysregulated Pathways Via Analysis of Clinical Expression Profiles.

Igor Ulitsky, Richard M. Karp, Ron Shamir

Proceedings of the Research in Computational Molecular Biology, 2008

2007

Special issue on computational molecular biology.

Richard M. Karp, Ming Li, Pavel A. Pevzner, Ron Shamir

J. Comput. Syst. Sci., 2007

Comparing Protein Interaction Networks via a Graph Match-and-Split Algorithm.

Manikandan Narayanan, Richard M. Karp

J. Comput. Biol., 2007

HAPLOPOOL: improving haplotype frequency estimation through DNA pools and phylogenetic modeling.

Bonnie Kirkpatrick, Carlos Santos Armendariz, Richard M. Karp, Eran Halperin

Bioinform., 2007

Computer Science as a Lens on the Sciences: .

Richard M. Karp

Proceedings of the 2007 IEEE / WIC / ACM International Conference on Web Intelligence, 2007

Noisy binary search and its applications.

Richard M. Karp, Robert Kleinberg

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Balancing traffic load in wireless networks with curveball routing.

Lucian Popa, Afshin Rostamizadeh, Richard M. Karp, Christos H. Papadimitriou, Ion Stoica

Proceedings of the 8th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2007

Streaming Algorithms for Selection and Approximate Sorting.

Richard M. Karp

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

Computer Science as a Lens on the Sciences: The Example of Computational Molecular Biology.

Richard M. Karp

Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine, 2007

2006

Reconstructing Chain Functions in Genetic Networks.

Irit Gat-Viks, Richard M. Karp, Ron Shamir, Roded Sharan

SIAM J. Discret. Math., 2006

Load balancing in dynamic structured peer-to-peer systems.

Sonesh Surana, Brighten Godfrey, Karthik Lakshminarayanan, Richard M. Karp, Ion Stoica

Perform. Evaluation, 2006

Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks.

Jacob Scott, Trey Ideker, Richard M. Karp, Roded Sharan

J. Comput. Biol., 2006

Fair Bandwidth Allocation Without Per-Flow State.

Richard M. Karp

Proceedings of the Theoretical Computer Science, 2006

2005

The minimum-entropy set cover problem.

Eran Halperin, Richard M. Karp

Theor. Comput. Sci., 2005

Guest Editors' foreword.

Richard M. Karp, Ming Li, Pavel A. Pevzner, Ron Shamir

J. Comput. Syst. Sci., 2005

Identification of Protein Complexes by Comparative Analysis of Yeast and Bacterial Protein Interaction Data.

Roded Sharan, Trey Ideker, Brian P. Kelley, Ron Shamir, Richard M. Karp

J. Comput. Biol., 2005

Optimal flow distribution among multiple channels with unknown capacities.

Richard M. Karp, Till Nierhoff, Till Tantau

Electron. Notes Discret. Math., 2005

Verification decoding of raptor codes.

Richard M. Karp, Michael Luby, Amin Shokrollahi

Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005

2004

MotifPrototyper: A Bayesian profile model for motif families.

Eric P. Xing, Richard M. Karp

Proc. Natl. Acad. Sci. USA, 2004

Towards Optimally Multiplexed Applications of Universal Arrays.

Amir Ben-Dor, Tzvika Hartman, Richard M. Karp, Benno Schwikowski, Roded Sharan, Zohar Yakhini

J. Comput. Biol., 2004

Logos: a Modular Bayesian Model for <i>de Novo</i> Motif Detection.

Eric P. Xing, Wei Wu, Michael I. Jordan, Richard M. Karp

J. Bioinform. Comput. Biol., 2004

The Role of Experimental Algorithms in Genomics.

Richard M. Karp

Proceedings of the Experimental and Efficient Algorithms, Third International Workshop, 2004

Gapped Local Similarity Search with Provable Guarantees.

Manikandan Narayanan, Richard M. Karp

Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004

Algorithms for inferring cis-regulatory structures and protein interaction networks.

Richard M. Karp

Proceedings of the Eighth Annual International Conference on Computational Molecular Biology, 2004

Perfect phylogeny and haplotype assignment.

Eran Halperin, Richard M. Karp

Proceedings of the Eighth Annual International Conference on Computational Molecular Biology, 2004

Global Synchronization in Sensornets.

Jeremy Elson, Richard M. Karp, Christos H. Papadimitriou, Scott Shenker

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Finite length analysis of LT codes.

Richard M. Karp, Michael Luby, Amin Shokrollahi

Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

Load Balancing in Dynamic Structured P2P Systems.

Brighten Godfrey, Karthik Lakshminarayanan, Sonesh Surana, Richard M. Karp, Ion Stoica

Proceedings of the Proceedings IEEE INFOCOM 2004, 2004

2003

A simple algorithm for finding frequent elements in streams and bags.

Richard M. Karp, Scott Shenker, Christos H. Papadimitriou

ACM Trans. Database Syst., 2003

Coalescing times for IID random variables with applications to population biology.

Ilan Adler, Hyun-Soo Ahn, Richard M. Karp, Sheldon M. Ross

Random Struct. Algorithms, 2003

The Restriction Scaffold Problem.

Amir Ben-Dor, Richard M. Karp, Benno Schwikowski, Ron Shamir

J. Comput. Biol., 2003

Discovering Local Structure in Gene Expression Data: The Order-Preserving Submatrix Problem.

Amir Ben-Dor, Benny Chor, Richard M. Karp, Zohar Yakhini

J. Comput. Biol., 2003

A stochastic process on the hypercube with applications to peer-to-peer networks.

Micah Adler, Eran Halperin, Richard M. Karp, Vijay V. Vazirani

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Large scale reconstruction of haplotypes from genotype data.

Eleazar Eskin, Eran Halperin, Richard M. Karp

Proceedings of the Sventh Annual International Conference on Computational Biology, 2003

A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding.

Richard M. Karp, Claire Kenyon

Proceedings of the Approximation, 2003

CREME: a framework for identifying cis-regulatory modules in human-mouse conserved segments.

Roded Sharan, Ivan Ovcharenko, Asa Ben-Hur, Richard M. Karp

Proceedings of the Eleventh International Conference on Intelligent Systems for Molecular Biology, June 29, 2003

Detecting protein sequence conservation via metric embeddings.

Eran Halperin, Jeremy Buhler, Richard M. Karp, Robert Krauthgamer, Ben Westover

Proceedings of the Eleventh International Conference on Intelligent Systems for Molecular Biology, June 29, 2003

Load Balancing in Structured P2P Systems.

Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard M. Karp, Ion Stoica

Proceedings of the Peer-to-Peer Systems II, Second International Workshop, 2003

LOGOS: a modular Bayesian model for de novo motif detection.

Eric P. Xing, Wei Wu, Michael I. Jordan, Richard M. Karp

Proceedings of the 2nd IEEE Computer Society Bioinformatics Conference, 2003

The Role of Algorithmic Research in Computational Genomics.

Richard M. Karp

Proceedings of the 2nd IEEE Computer Society Bioinformatics Conference, 2003

2002

The Efficiency of Resolution and Davis--Putnam Procedures.

Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks

SIAM J. Comput., 2002

Selfish behavior and stability of the internet: a game-theoretic analysis of TCP.

Aditya Akella, Srinivasan Seshan, Richard M. Karp, Scott Shenker, Christos H. Papadimitriou

Proceedings of the ACM SIGCOMM 2002 Conference on Applications, 2002

A Hierarchical Bayesian Markovian Model for Motifs in Biopolymer Sequences.

Eric P. Xing, Michael I. Jordan, Richard M. Karp, Stuart Russell

Proceedings of the Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, 2002

Topologically-Aware Overlay Construction and Server Selection.

Sylvia Ratnasamy, Mark Handley, Richard M. Karp, Scott Shenker

Proceedings of the Proceedings IEEE INFOCOM 2002, 2002

2001

Algorithms for graph partitioning on the planted partition model.

Anne Condon, Richard M. Karp

Random Struct. Algorithms, 2001

Optimal Search and One-Way Trading Online Algorithms.

Ran El-Yaniv, Amos Fiat, Richard M. Karp, G. Turpin

Algorithmica, 2001

A scalable content-addressable network.

Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard M. Karp, Scott Shenker

Proceedings of the ACM SIGCOMM 2001 Conference on Applications, 2001

Application-Level Multicast Using Content-Addressable Networks.

Sylvia Ratnasamy, Mark Handley, Richard M. Karp, Scott Shenker

Proceedings of the Networked Group Communication, 2001

CLIFF: clustering of high-dimensional microarray data via iterative feature filtering using normalized cuts.

Eric P. Xing, Richard M. Karp

Proceedings of the Ninth International Conference on Intelligent Systems for Molecular Biology, 2001

Feature selection for high-dimensional genomic microarray data.

Eric P. Xing, Michael I. Jordan, Richard M. Karp

Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), Williams College, Williamstown, MA, USA, June 28, 2001

The Genomics Revolution and its Challenges for Algorithmic Research.

Richard M. Karp

Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000

An Optimal Algorithm for Monte Carlo Estimation.

Paul Dagum, Richard M. Karp, Michael Luby, Sheldon M. Ross

SIAM J. Comput., 2000

Parallel Sorting with Limited Bandwidth.

Micah Adler, John W. Byers, Richard M. Karp

SIAM J. Comput., 2000

Algorithms for Optical Mapping.

Richard M. Karp, Ron Shamir

J. Comput. Biol., 2000

An Algorithm Combining Discrete and Continuous Methods for Optical Mapping.

Richard M. Karp, Itsik Pe'er, Ron Shamir

J. Comput. Biol., 2000

Universal DNA Tag Systems: A Combinatorial Design Scheme.

Amir Ben-Dor, Richard M. Karp, Benno Schwikowski, Zohar Yakhini

J. Comput. Biol., 2000

The Genomics Revolution and Its Challenges for Algorithmic Research.

Richard M. Karp

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Randomized Rumor Spreading.

Richard M. Karp, Christian Schindelhauer, Scott Shenker, Berthold Vöcking

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Optimization Problems in Congestion Control.

Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Error-resilient DNA computation.

Richard M. Karp, Claire Kenyon, Orli Waarts

Random Struct. Algorithms, 1999

An Algorithmic Approach to Multiple Complete Digest Mapping.

Daniel P. Fasulo, Tao Jiang, Richard M. Karp, Reuben J. Settergren, Edward C. Thayer

J. Comput. Biol., 1999

Algorithms for choosing differential gene expression experiments.

Richard M. Karp, Roland Stoughton, Ka Yee Yeung

Proceedings of the Third Annual International Conference on Research in Computational Molecular Biology, 1999

1998

On Parallel Evaluation of Game Trees.

Richard M. Karp, Yanjun Zhang

J. ACM, 1998

Graph Traversals, Genes and Matroids: An Efficient Case of the Travelling Salesman Problem.

Dan Gusfield, Richard M. Karp, Lusheng Wang, Paul Stelling

Discret. Appl. Math., 1998

Mapping Clones with a Given Ordering or Interleaving.

Tao Jiang, Richard M. Karp

Algorithmica, 1998

On the Complexity of Unsatisfiability Proofs for Random <i>k</i>-CNF Formulas.

Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Random Graphs, Random Walks, Differential Equations and the Probabilistic Analysis of Algorithms.

Richard M. Karp

Proceedings of the STACS 98, 1998

Constructing maps using the span and inclusion relations.

Daniel P. Fasulo, Tao Jiang, Richard M. Karp, Nitin Sharma

Proceedings of the Second Annual International Conference on Research in Computational Molecular Biology, 1998

1997

Emerging opportunities for theoretical computer science.

Alfred V. Aho, David S. Johnson, Richard M. Karp, S. Rao Kosaraju, Catherine C. McGeoch, Christos H. Papadimitriou, Pavel A. Pevzner

SIGACT News, 1997

The rank of sparse random matrices over finite fields.

Johannes Blömer, Richard M. Karp, Emo Welzl

Random Struct. Algorithms, 1997

Nearly Optimal Competitive Online Replacement Policies.

Ran El-Yaniv, Richard M. Karp

Math. Oper. Res., 1997

Mapping Clones with a Given Ordering or Interleaving (Extended Abstract).

Tao Jiang, Richard M. Karp

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Mapping clones with a given ordering or interleaving (abstract).

Tao Jiang, Richard M. Karp

Proceedings of the First Annual International Conference on Research in Computational Molecular Biology, 1997

Fast and Intuitive Clustering of Web Documents.

Oren Zamir, Oren Etzioni, Omid Madani, Richard M. Karp

Proceedings of the Third International Conference on Knowledge Discovery and Data Mining (KDD-97), 1997

1996

LogP: A Practical Model of Parallel Computation.

David E. Culler, Richard M. Karp, David A. Patterson, Abhijit Sahay, Eunice E. Santos, Klaus E. Schauser, Ramesh Subramonian, Thorsten von Eicken

Commun. ACM, 1996

Efficient PRAM Simulation on a Distributed Memory Machine.

Richard M. Karp, Michael Luby, Friedhelm Meyer auf der Heide

Algorithmica, 1996

A Method for Obtaining Randomized Algorithms with Small Tail Probabilities.

Helmut Alt, Leonidas J. Guibas, Kurt Mehlhorn, Richard M. Karp, Avi Wigderson

Algorithmica, 1996

Efficient Information Gathering on the Internet (extended abstract).

Oren Etzioni, Steve Hanks, Tao Jiang, Richard M. Karp, Omid Madani, Orli Waarts

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?

Alan M. Frieze, Richard M. Karp, Bruce A. Reed

SIAM J. Comput., 1995

A Graph-Theoretic Game and Its Application to the k-Server Problem.

Noga Alon, Richard M. Karp, David Peleg, Douglas B. West

SIAM J. Comput., 1995

Bounded Branching Process AND/OR Tree Evaluation.

Richard M. Karp, Yanjun Zhang

Random Struct. Algorithms, 1995

Physical Mapping of Chromosomes Using Unique Probes.

Farid Alizadeh, Richard M. Karp, Deborah K. Weisser, Geoffrey Zweig

J. Comput. Biol., 1995

An algorithm for analysing probed partial digestion experiments.

Richard M. Karp, Lee Aaron Newberg

Comput. Appl. Biosci., 1995

Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology.

Farid Alizadeh, Richard M. Karp, Lee Aaron Newberg, Deborah K. Weisser

Algorithmica, 1995

Scheduling Parallel Communication: The h-relation Problem.

Micah Adler, John W. Byers, Richard M. Karp

Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

Modeling parallel communication.

Richard M. Karp

Proceedings of IPPS '95, 1995

The Bit Vector Intersection Problem (Preliminary Version).

Richard M. Karp, Orli Waarts, Geoffrey Zweig

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract).

Paul Dagum, Richard M. Karp, Michael Luby, Sheldon M. Ross

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Average Case Analysis of a Heuristic for the Assignment Problem.

Richard M. Karp, Alexander H. G. Rinnooy Kan, Rakesh V. Vohra

Math. Oper. Res., 1994

Probabilistic Recurrence Relations.

Richard M. Karp

J. ACM, 1994

Coding Techniques for Handling Failures in Large Disk Arrays.

Lisa Hellerstein, Garth A. Gibson, Richard M. Karp, Randy H. Katz, David A. Patterson

Algorithmica, 1994

On the Power of Randomization in On-Line Algorithms.

Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson

Algorithmica, 1994

Selection in the Presence of Noise: The Design of Playoff Systems.

Micah Adler, Peter Gemmell, Mor Harchol-Balter, Richard M. Karp, Claire Kenyon

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

A Monte-Carlo Algorithm for Estimating the Permanent.

Narendra Karmarkar, Richard M. Karp, Richard J. Lipton, László Lovász, Michael Luby

SIAM J. Comput., 1993

Probabilistic Analysis of Network Flow Algorithms.

Richard M. Karp, Rajeev Motwani, Noam Nisan

Math. Oper. Res., 1993

Randomized Parallel Algorithms for Backtrack Search and Branch-and-Bound Computation.

Richard M. Karp, Yanjun Zhang

J. ACM, 1993

A Generalization of Binary Search.

Richard M. Karp

Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Mapping the genome: some combinatorial problems arising in molecular biology.

Richard M. Karp

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Optimal Broadcast and Summation in the LogP Model.

Richard M. Karp, Abhijit Sahay, Eunice E. Santos, Klaus E. Schauser

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

LogP: Towards a Realistic Model of Parallel Computation.

David E. Culler, Richard M. Karp, David A. Patterson, Abhijit Sahay, Klaus E. Schauser, Eunice E. Santos, Ramesh Subramonian, Thorsten von Eicken

Proceedings of the Fourth ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming (PPOPP), 1993

The Mortgage Problem.

Ran El-Yaniv, Richard M. Karp

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

1992

Three-Stage Generalized Connectors.

Richard M. Karp

SIAM J. Discret. Math., 1992

On-Line Algorithms Versus Off-Line Algorithms: How Much is it Worth to Know the Future?

Richard M. Karp

Proceedings of the Algorithms, Software, Architecture, 1992

Competitive Analysis of Financial Games

Ran El-Yaniv, Amos Fiat, Richard M. Karp, G. Turpin

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Transitive Compaction in Parallel via Branchings.

Phillip B. Gibbons, Richard M. Karp, Vijaya Ramachandran, Danny Soroker, Robert Endre Tarjan

J. Algorithms, 1991

Competitive Paging Algorithms.

Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, Neal E. Young

J. Algorithms, 1991

An introduction to randomized algorithms.

Richard M. Karp

Discret. Appl. Math., 1991

FFD Bin Packing for Item Sizes with Uniform Distributions on [0, 1/2].

Sally Floyd, Richard M. Karp

Algorithmica, 1991

A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract).

Noga Alon, Richard M. Karp, David Peleg, Douglas B. West

Proceedings of the On-Line Algorithms, 1991

1990

The Transitive Closure of a Random Digraph.

Richard M. Karp

Random Struct. Algorithms, 1990

Subtree isomorphism is in random NC.

Phillip B. Gibbons, Richard M. Karp, Gary L. Miller, Danny Soroker

Discret. Appl. Math., 1990

An Optimal Algorithm for On-line Bipartite Matching

Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

On the Power of Randomization in Online Algorithms (Extended Abstract)

Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Parallel Algorithms for Shared-Memory Machines.

Richard M. Karp, Vijaya Ramachandran

Proceedings of the Handbook of Theoretical Computer Science, 1990

1989

Monte-Carlo Approximation Algorithms for Enumeration Problems.

Richard M. Karp, Michael Luby, Neal Madras

J. Algorithms, 1989

Failure Correction Techniques for Large Disk Arrays.

Garth A. Gibson, Lisa Hellerstein, Richard M. Karp, Randy H. Katz, David A. Patterson

Proceedings of the ASPLOS-III Proceedings, 1989

1988

Deferred Data Structuring.

Richard M. Karp, Rajeev Motwani, Prabhakar Raghavan

SIAM J. Comput., 1988

The Complexity of Parallel Search.

Richard M. Karp, Eli Upfal, Avi Wigderson

J. Comput. Syst. Sci., 1988

A Randomized Parallel Branch-and-Bound Procedure

Richard M. Karp, Yanjun Zhang

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1987

A simplex variant solving an <i>m</i> times <i>d</i> linear program in <i>O(min(m², d²)</i> expected number of pivot steps.

Ilan Adler, Richard M. Karp, Ron Shamir

J. Complex., 1987

Efficient Randomized Pattern-Matching Algorithms.

Richard M. Karp, Michael O. Rabin

IBM J. Res. Dev., 1987

Global Wire Routing in Two-Dimensional Arrays.

Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani

Algorithmica, 1987

1986

A Family of Simplex Variants Solving an <i>m</i> × <i>d</i> Linear Program in Expected Number of Pivot Steps Depending on <i>d</i> Only.

Ilan Adler, Richard M. Karp, Ron Shamir

Math. Oper. Res., 1986

Constructing a perfect matching is in random NC.

Richard M. Karp, Eli Upfal, Avi Wigderson

Comb., 1986

Combinatorics, Complexity, and Randomness.

Richard M. Karp

Commun. ACM, 1986

On a Search Problem Related to Branch-and-Bound Procedures

Richard M. Karp, Michael E. Saks, Avi Wigderson

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

FFD Bin Packing for Item Sizes with Distributions on [0,1/2]

Sally Floyd, Richard M. Karp

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985

A Fast Parallel Algorithm for the Maximal Independent Set Problem

Richard M. Karp, Avi Wigderson

J. ACM, October, 1985

Monte-Carlo algorithms for the planar multiterminal network reliability problem.

Richard M. Karp, Michael Luby

J. Complex., 1985

Are Search and Decision Problems Computationally Equivalent?

Richard M. Karp, Eli Upfal, Avi Wigderson

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

The Complexity of Parallel Computation on Matroids

Richard M. Karp, Eli Upfal, Avi Wigderson

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Turing award lecture.

Richard M. Karp

Proceedings of the 1985 ACM annual conference on The range of computing: mid-80's perspective: mid-80's perspective, 1985

1984

A Probabilistic Analysis of Multidimensional Bin Packing Problems

Richard M. Karp, Michael Luby, Alberto Marchetti-Spaccamela

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983

Searching for an Optimal Path in a Tree with Random Costs.

Richard M. Karp, Judea Pearl

Artif. Intell., 1983

Global Wire Routing in Two-Dimensional Arrays (Extended Abstract)

Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Monte-Carlo Algorithms for Enumeration and Reliability Problems

Richard M. Karp, Michael Luby

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982

On Linear Characterizations of Combinatorial Optimization Problems.

Richard M. Karp, Christos H. Papadimitriou

SIAM J. Comput., 1982

Dynamic programming meets the principle of inclusion and exclusion.

Richard M. Karp

Oper. Res. Lett., 1982

On the Security of Ping-Pong Protocols

Danny Dolev, Shimon Even, Richard M. Karp

Inf. Control., 1982

An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem

Narendra Karmarkar, Richard M. Karp

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981

The Complexity of Testing Whether a Graph is a Superconcentrator.

Manuel Blum, Richard M. Karp, Oliver Vornberger, Christos H. Papadimitriou, Mihalis Yannakakis

Inf. Process. Lett., 1981

Parametric shortest path algorithms with an application to cyclic staffing.

Richard M. Karp, James B. Orlin

Discret. Appl. Math., 1981

Maximum Matchings in Sparse Random Graphs

Richard M. Karp, Michael Sipser

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980

An algorithm to solve the <i>m</i> × <i>n</i> assignment problem in expected time <i>O</i>(<i>mn</i> log <i>n</i>).

Richard M. Karp

Networks, 1980

Linear Expected-Time Algorithms for Connectivity Problems.

Richard M. Karp, Robert Endre Tarjan

J. Algorithms, 1980

Linear Expected-Time Algorithms for Connectivity Problems (Extended Abstract)

Richard M. Karp, Robert Endre Tarjan

Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

Some Connections between Nonuniform and Uniform Complexity Classes

Richard M. Karp, Richard J. Lipton

Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979

A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem.

Richard M. Karp

SIAM J. Comput., 1979

Recent Advances in the Probabilistic Analysis of Graph-Theoretic Algorithms (Abstract).

Richard M. Karp

Proceedings of the Automata, 1979

Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems

Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, Charles Rackoff

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978

A characterization of the minimum cycle mean in a digraph.

Richard M. Karp

Discret. Math., 1978

1977

Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane.

Richard M. Karp

Math. Oper. Res., 1977

1975

Near-Optimal Solutions to a 2-Dimensional Placement Problem.

Richard M. Karp, A. C. McKellar, C. K. Wong

SIAM J. Comput., 1975

On the Computational Complexity of Combinatorial Problems.

Richard M. Karp

Networks, 1975

Two special cases of the assignment problem.

Richard M. Karp, Shuo-Yen Robert Li

Discret. Math., 1975

1973

An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs.

John E. Hopcroft, Richard M. Karp

SIAM J. Comput., 1973

1972

A Phenomenon in the Theory of Sorting.

David Gale, Richard M. Karp

J. Comput. Syst. Sci., 1972

Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.

Jack Edmonds, Richard M. Karp

J. ACM, 1972

Rapid Identification of Repeated Patterns in Strings, Trees and Arrays

Richard M. Karp, Raymond E. Miller, Arnold L. Rosenberg

Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972

Reducibility Among Combinatorial Problems.

Richard M. Karp

Proceedings of a symposium on the Complexity of Computer Computations, 1972

Large scale optimization and the relaxation method.

Michael Held, Richard M. Karp, Philip Wolfe

Proceedings of the ACM annual conference, 1972

1971

A simple derivation of Edmonds' algorithm for optimum branchings.

Richard M. Karp

Networks, 1971

The traveling-salesman problem and minimum spanning trees: Part II.

Michael Held, Richard M. Karp

Math. Program., 1971

A n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs

John E. Hopcroft, Richard M. Karp

Proceedings of the 12th Annual Symposium on Switching and Automata Theory, 1971

1970

The Traveling-Salesman Problem and Minimum Spanning Trees.

Michael Held, Richard M. Karp

Oper. Res., 1970

1969

Parallel Program Schemata.

Richard M. Karp, Raymond E. Miller

J. Comput. Syst. Sci., 1969

1967

The Organization of Computations for Uniform Recurrence Equations.

Richard M. Karp, Raymond E. Miller, Shmuel Winograd

J. ACM, 1967

Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines.

Richard M. Karp

J. ACM, 1967

Parallel Program Schemata: A Mathematical Model for Parallel Computation

Richard M. Karp, Raymond E. Miller

Proceedings of the 8th Annual Symposium on Switching and Automata Theory, 1967

1966

Index Register Allocation.

Lawrence Paul Horwitz, Richard M. Karp, Raymond E. Miller, Shmuel Winograd

J. ACM, 1966

1965

The Construction of Discrete Dynamic Programming Algorithms.

Michael Held, Richard M. Karp

IBM Syst. J., 1965

1964

Some Techniques of State Assignment for Synchronous Sequential Machines.

Richard M. Karp

IEEE Trans. Electron. Comput., 1964

1962

Minimization Over Boolean Graphs.

J. Paul Roth, Richard M. Karp

IBM J. Res. Dev., 1962

1961

Minimum-redundancy coding for the discrete noiseless channel.

Richard M. Karp

IRE Trans. Inf. Theory, 1961

A computer program for the synthesis of combinational switching circuits

Richard M. Karp, F. E. McFarlin, J. Paul Roth, J. R. Wilts

Proceedings of the 2nd Annual Symposium on Switching Circuit Theory and Logical Design, 1961

A dynamic programming approach to sequencing problems.

Michael Held, Richard M. Karp

Proceedings of the 16th ACM national meeting, 1961

1960

A Note on the Applicaton of Graph Theory to Digital Computer Programming

Richard M. Karp

Inf. Control., June, 1960