Richard M. Karp

Affiliations:
  • University of California, Berkeley, USA


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

Collaborative distances:
  • Dijkstra number2 of two.
  • Erdős number3 of two.

Awards

Turing Prize recipient

Turing Prize 1985, "For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness".

ACM Fellow

ACM Fellow 1994, "For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial -time computability with the intuitive notion".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2019
Massively Parallel Computation of Matching and MIS in Sparse Graphs.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

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

2017
Random Knockout Tournaments.
Oper. Res., 2017

2014
Finding a most biased coin with fewest flips.
Proceedings of The 27th Conference on Learning Theory, 2014

2013
Reconstructing Boolean Models of Signaling.
J. Comput. Biol., 2013

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

2012
Algorithms to Detect Multiprotein Modularity Conserved during Evolution.
IEEE ACM Trans. Comput. Biol. Bioinform., 2012

Comparing Pedigree Graphs.
J. Comput. Biol., 2012

Theory of Computation as an Enabling Tool for the Sciences.
Proceedings of the Theory and Applications of Models of Computation, 2012

Algorithmic methodologies for ultra-efficient inexact architectures for sustaining technology scaling.
Proceedings of the Computing Frontiers Conference, CF'12, 2012

An Algorithmic View of the Universe.
Proceedings of the ACM Turing Centenary Celebration, 2012

2011
Sorting and Selection in Posets.
SIAM J. Comput., 2011

Understanding Science Through the Computational Lens.
J. Comput. Sci. Technol., 2011

Heuristic algorithms in computational molecular biology.
J. Comput. Syst. Sci., 2011

Pedigree Reconstruction Using Identity by Descent.
J. Comput. Biol., 2011

Faster and More Accurate Sequence Alignment with SNAP
CoRR, 2011

Algorithms for Implicit Hitting Set Problems.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010
Haplotype Inference in Complex Pedigrees.
J. Comput. Biol., 2010

Topology-Free Querying of Protein Interaction Networks.
J. Comput. Biol., 2010

Algorithms for Comparing Pedigree Graphs
CoRR, 2010

Prediction of Phenotype Information from Genotype Data.
Commun. Inf. Syst., 2010

Implicit Hitting Set Problems and Multi-genome Alignment.
Proceedings of the Combinatorial Pattern Matching, 21st Annual Symposium, 2010

Reducibility Among Combinatorial Problems.
Proceedings of the 50 Years of Integer Programming 1958-2008, 2010

2009
Torque: topology-free querying of protein interaction networks.
Nucleic Acids Res., 2009

On the Price of Heterogeneity in Parallel Systems.
Theory Comput. Syst., 2009

My memories of David Gale.
Games Econ. Behav., 2009

Haplotype Inference in Complex Pedigrees.
Proceedings of the Research in Computational Molecular Biology, 2009

2008
Probabilistic Analysis of Linear Programming Decoding.
IEEE Trans. Inf. Theory, 2008

George Dantzig's impact on the theory of computation.
Discret. Optim., 2008

Linked decompositions of networks and the power of choice in Polya urns.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Detecting Disease-Specific Dysregulated Pathways Via Analysis of Clinical Expression Profiles.
Proceedings of the Research in Computational Molecular Biology, 2008

2007
Special issue on computational molecular biology.
J. Comput. Syst. Sci., 2007

Comparing Protein Interaction Networks via a Graph Match-and-Split Algorithm.
J. Comput. Biol., 2007

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

Computer Science as a Lens on the Sciences: .
Proceedings of the 2007 IEEE / WIC / ACM International Conference on Web Intelligence, 2007

Noisy binary search and its applications.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Balancing traffic load in wireless networks with curveball routing.
Proceedings of the 8th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2007

Streaming Algorithms for Selection and Approximate Sorting.
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.
Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine, 2007

2006
Reconstructing Chain Functions in Genetic Networks.
SIAM J. Discret. Math., 2006

Load balancing in dynamic structured peer-to-peer systems.
Perform. Evaluation, 2006

Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks.
J. Comput. Biol., 2006

Fair Bandwidth Allocation Without Per-Flow State.
Proceedings of the Theoretical Computer Science, 2006

2005
The minimum-entropy set cover problem.
Theor. Comput. Sci., 2005

Guest Editors' foreword.
J. Comput. Syst. Sci., 2005

Identification of Protein Complexes by Comparative Analysis of Yeast and Bacterial Protein Interaction Data.
J. Comput. Biol., 2005

Optimal flow distribution among multiple channels with unknown capacities.
Electron. Notes Discret. Math., 2005

Verification decoding of raptor codes.
Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005

2004
MotifPrototyper: A Bayesian profile model for motif families.
Proc. Natl. Acad. Sci. USA, 2004

Towards Optimally Multiplexed Applications of Universal Arrays.
J. Comput. Biol., 2004

Logos: a Modular Bayesian Model for <i>de Novo</i> Motif Detection.
J. Bioinform. Comput. Biol., 2004

The Role of Experimental Algorithms in Genomics.
Proceedings of the Experimental and Efficient Algorithms, Third International Workshop, 2004

Gapped Local Similarity Search with Provable Guarantees.
Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004

Algorithms for inferring cis-regulatory structures and protein interaction networks.
Proceedings of the Eighth Annual International Conference on Computational Molecular Biology, 2004

Perfect phylogeny and haplotype assignment.
Proceedings of the Eighth Annual International Conference on Computational Molecular Biology, 2004

Global Synchronization in Sensornets.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Finite length analysis of LT codes.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

Load Balancing in Dynamic Structured P2P Systems.
Proceedings of the Proceedings IEEE INFOCOM 2004, 2004

2003
A simple algorithm for finding frequent elements in streams and bags.
ACM Trans. Database Syst., 2003

Coalescing times for IID random variables with applications to population biology.
Random Struct. Algorithms, 2003

The Restriction Scaffold Problem.
J. Comput. Biol., 2003

Discovering Local Structure in Gene Expression Data: The Order-Preserving Submatrix Problem.
J. Comput. Biol., 2003

A stochastic process on the hypercube with applications to peer-to-peer networks.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Large scale reconstruction of haplotypes from genotype data.
Proceedings of the Sventh Annual International Conference on Computational Biology, 2003

A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding.
Proceedings of the Approximation, 2003

CREME: a framework for identifying cis-regulatory modules in human-mouse conserved segments.
Proceedings of the Eleventh International Conference on Intelligent Systems for Molecular Biology, June 29, 2003

Detecting protein sequence conservation via metric embeddings.
Proceedings of the Eleventh International Conference on Intelligent Systems for Molecular Biology, June 29, 2003

Load Balancing in Structured P2P Systems.
Proceedings of the Peer-to-Peer Systems II, Second International Workshop, 2003

LOGOS: a modular Bayesian model for de novo motif detection.
Proceedings of the 2nd IEEE Computer Society Bioinformatics Conference, 2003

The Role of Algorithmic Research in Computational Genomics.
Proceedings of the 2nd IEEE Computer Society Bioinformatics Conference, 2003

2002
The Efficiency of Resolution and Davis--Putnam Procedures.
SIAM J. Comput., 2002

Selfish behavior and stability of the internet: a game-theoretic analysis of TCP.
Proceedings of the ACM SIGCOMM 2002 Conference on Applications, 2002

A Hierarchical Bayesian Markovian Model for Motifs in Biopolymer Sequences.
Proceedings of the Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, 2002

Topologically-Aware Overlay Construction and Server Selection.
Proceedings of the Proceedings IEEE INFOCOM 2002, 2002

2001
Algorithms for graph partitioning on the planted partition model.
Random Struct. Algorithms, 2001

Optimal Search and One-Way Trading Online Algorithms.
Algorithmica, 2001

A scalable content-addressable network.
Proceedings of the ACM SIGCOMM 2001 Conference on Applications, 2001

Application-Level Multicast Using Content-Addressable Networks.
Proceedings of the Networked Group Communication, 2001

CLIFF: clustering of high-dimensional microarray data via iterative feature filtering using normalized cuts.
Proceedings of the Ninth International Conference on Intelligent Systems for Molecular Biology, 2001

Feature selection for high-dimensional genomic microarray data.
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.
Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000
An Optimal Algorithm for Monte Carlo Estimation.
SIAM J. Comput., 2000

Parallel Sorting with Limited Bandwidth.
SIAM J. Comput., 2000

Algorithms for Optical Mapping.
J. Comput. Biol., 2000

An Algorithm Combining Discrete and Continuous Methods for Optical Mapping.
J. Comput. Biol., 2000

Universal DNA Tag Systems: A Combinatorial Design Scheme.
J. Comput. Biol., 2000

The Genomics Revolution and Its Challenges for Algorithmic Research.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Randomized Rumor Spreading.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Optimization Problems in Congestion Control.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Error-resilient DNA computation.
Random Struct. Algorithms, 1999

An Algorithmic Approach to Multiple Complete Digest Mapping.
J. Comput. Biol., 1999

Algorithms for choosing differential gene expression experiments.
Proceedings of the Third Annual International Conference on Research in Computational Molecular Biology, 1999

1998
On Parallel Evaluation of Game Trees.
J. ACM, 1998

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

Mapping Clones with a Given Ordering or Interleaving.
Algorithmica, 1998

On the Complexity of Unsatisfiability Proofs for Random <i>k</i>-CNF Formulas.
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.
Proceedings of the STACS 98, 1998

Constructing maps using the span and inclusion relations.
Proceedings of the Second Annual International Conference on Research in Computational Molecular Biology, 1998

1997
Emerging opportunities for theoretical computer science.
SIGACT News, 1997

The rank of sparse random matrices over finite fields.
Random Struct. Algorithms, 1997

Nearly Optimal Competitive Online Replacement Policies.
Math. Oper. Res., 1997

Mapping Clones with a Given Ordering or Interleaving (Extended Abstract).
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Mapping clones with a given ordering or interleaving (abstract).
Proceedings of the First Annual International Conference on Research in Computational Molecular Biology, 1997

Fast and Intuitive Clustering of Web Documents.
Proceedings of the Third International Conference on Knowledge Discovery and Data Mining (KDD-97), 1997

1996
LogP: A Practical Model of Parallel Computation.
Commun. ACM, 1996

Efficient PRAM Simulation on a Distributed Memory Machine.
Algorithmica, 1996

A Method for Obtaining Randomized Algorithms with Small Tail Probabilities.
Algorithmica, 1996

Efficient Information Gathering on the Internet (extended abstract).
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?
SIAM J. Comput., 1995

A Graph-Theoretic Game and Its Application to the k-Server Problem.
SIAM J. Comput., 1995

Bounded Branching Process AND/OR Tree Evaluation.
Random Struct. Algorithms, 1995

Physical Mapping of Chromosomes Using Unique Probes.
J. Comput. Biol., 1995

An algorithm for analysing probed partial digestion experiments.
Comput. Appl. Biosci., 1995

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

Scheduling Parallel Communication: The h-relation Problem.
Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

Modeling parallel communication.
Proceedings of IPPS '95, 1995

The Bit Vector Intersection Problem (Preliminary Version).
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract).
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
Average Case Analysis of a Heuristic for the Assignment Problem.
Math. Oper. Res., 1994

Probabilistic Recurrence Relations.
J. ACM, 1994

Coding Techniques for Handling Failures in Large Disk Arrays.
Algorithmica, 1994

On the Power of Randomization in On-Line Algorithms.
Algorithmica, 1994

Selection in the Presence of Noise: The Design of Playoff Systems.
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.
SIAM J. Comput., 1993

Probabilistic Analysis of Network Flow Algorithms.
Math. Oper. Res., 1993

Randomized Parallel Algorithms for Backtrack Search and Branch-and-Bound Computation.
J. ACM, 1993

A Generalization of Binary Search.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Mapping the genome: some combinatorial problems arising in molecular biology.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Optimal Broadcast and Summation in the LogP Model.
Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

LogP: Towards a Realistic Model of Parallel Computation.
Proceedings of the Fourth ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming (PPOPP), 1993

The Mortgage Problem.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

1992
Three-Stage Generalized Connectors.
SIAM J. Discret. Math., 1992

On-Line Algorithms Versus Off-Line Algorithms: How Much is it Worth to Know the Future?
Proceedings of the Algorithms, Software, Architecture, 1992

Competitive Analysis of Financial Games
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
Transitive Compaction in Parallel via Branchings.
J. Algorithms, 1991

Competitive Paging Algorithms.
J. Algorithms, 1991

An introduction to randomized algorithms.
Discret. Appl. Math., 1991

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

A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract).
Proceedings of the On-Line Algorithms, 1991

1990
The Transitive Closure of a Random Digraph.
Random Struct. Algorithms, 1990

Subtree isomorphism is in random NC.
Discret. Appl. Math., 1990

An Optimal Algorithm for On-line Bipartite Matching
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

On the Power of Randomization in Online Algorithms (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Parallel Algorithms for Shared-Memory Machines.
Proceedings of the Handbook of Theoretical Computer Science, 1990

1989
Monte-Carlo Approximation Algorithms for Enumeration Problems.
J. Algorithms, 1989

Failure Correction Techniques for Large Disk Arrays.
Proceedings of the ASPLOS-III Proceedings, 1989

1988
Deferred Data Structuring.
SIAM J. Comput., 1988

The Complexity of Parallel Search.
J. Comput. Syst. Sci., 1988

A Randomized Parallel Branch-and-Bound Procedure
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<sup>2</sup>, d<sup>2</sup>)</i> expected number of pivot steps.
J. Complex., 1987

Efficient Randomized Pattern-Matching Algorithms.
IBM J. Res. Dev., 1987

Global Wire Routing in Two-Dimensional Arrays.
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.
Math. Oper. Res., 1986

Constructing a perfect matching is in random NC.
Comb., 1986

Combinatorics, Complexity, and Randomness.
Commun. ACM, 1986

On a Search Problem Related to Branch-and-Bound Procedures
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

FFD Bin Packing for Item Sizes with Distributions on [0,1/2]
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
A Fast Parallel Algorithm for the Maximal Independent Set Problem
J. ACM, October, 1985

Monte-Carlo algorithms for the planar multiterminal network reliability problem.
J. Complex., 1985

Are Search and Decision Problems Computationally Equivalent?
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

The Complexity of Parallel Computation on Matroids
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Turing award lecture.
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
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.
Artif. Intell., 1983

Global Wire Routing in Two-Dimensional Arrays (Extended Abstract)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Monte-Carlo Algorithms for Enumeration and Reliability Problems
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982
On Linear Characterizations of Combinatorial Optimization Problems.
SIAM J. Comput., 1982

Dynamic programming meets the principle of inclusion and exclusion.
Oper. Res. Lett., 1982

On the Security of Ping-Pong Protocols
Inf. Control., 1982

An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981
The Complexity of Testing Whether a Graph is a Superconcentrator.
Inf. Process. Lett., 1981

Parametric shortest path algorithms with an application to cyclic staffing.
Discret. Appl. Math., 1981

Maximum Matchings in Sparse Random Graphs
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>).
Networks, 1980

Linear Expected-Time Algorithms for Connectivity Problems.
J. Algorithms, 1980

Linear Expected-Time Algorithms for Connectivity Problems (Extended Abstract)
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

Some Connections between Nonuniform and Uniform Complexity Classes
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979
A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem.
SIAM J. Comput., 1979

Recent Advances in the Probabilistic Analysis of Graph-Theoretic Algorithms (Abstract).
Proceedings of the Automata, 1979

Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
A characterization of the minimum cycle mean in a digraph.
Discret. Math., 1978

1977
Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane.
Math. Oper. Res., 1977

1975
Near-Optimal Solutions to a 2-Dimensional Placement Problem.
SIAM J. Comput., 1975

On the Computational Complexity of Combinatorial Problems.
Networks, 1975

Two special cases of the assignment problem.
Discret. Math., 1975

1973
An n<sup>5/2</sup> Algorithm for Maximum Matchings in Bipartite Graphs.
SIAM J. Comput., 1973

1972
A Phenomenon in the Theory of Sorting.
J. Comput. Syst. Sci., 1972

Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.
J. ACM, 1972

Rapid Identification of Repeated Patterns in Strings, Trees and Arrays
Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972

Reducibility Among Combinatorial Problems.
Proceedings of a symposium on the Complexity of Computer Computations, 1972

Large scale optimization and the relaxation method.
Proceedings of the ACM annual conference, 1972

1971
A simple derivation of Edmonds' algorithm for optimum branchings.
Networks, 1971

The traveling-salesman problem and minimum spanning trees: Part II.
Math. Program., 1971

A n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs
Proceedings of the 12th Annual Symposium on Switching and Automata Theory, 1971

1970
The Traveling-Salesman Problem and Minimum Spanning Trees.
Oper. Res., 1970

1969
Parallel Program Schemata.
J. Comput. Syst. Sci., 1969

1967
The Organization of Computations for Uniform Recurrence Equations.
J. ACM, 1967

Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines.
J. ACM, 1967

Parallel Program Schemata: A Mathematical Model for Parallel Computation
Proceedings of the 8th Annual Symposium on Switching and Automata Theory, 1967

1966
Index Register Allocation.
J. ACM, 1966

1965
The Construction of Discrete Dynamic Programming Algorithms.
IBM Syst. J., 1965

1964
Some Techniques of State Assignment for Synchronous Sequential Machines.
IEEE Trans. Electron. Comput., 1964

1962
Minimization Over Boolean Graphs.
IBM J. Res. Dev., 1962

1961
Minimum-redundancy coding for the discrete noiseless channel.
IRE Trans. Inf. Theory, 1961

A computer program for the synthesis of combinational switching circuits
Proceedings of the 2nd Annual Symposium on Switching Circuit Theory and Logical Design, 1961

A dynamic programming approach to sequencing problems.
Proceedings of the 16th ACM national meeting, 1961

1960
A Note on the Applicaton of Graph Theory to Digital Computer Programming
Inf. Control., June, 1960


  Loading...