462 citations · 783 across the 9 of their papers we have counts for
9 papers
Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +1
The success of modern parallel paradigms such as MapReduce, Hadoop, or Spark, has attracted a significant attention to the Massively Parallel Computation (MPC) model over the past…
Random Knockout Tournaments
Ilan Adler, Yang Cao, Richard Karp +2
We consider a random knockout tournament among players , in which each match involves two players. The match format is specified by the number of matches played in ea…
Faster and More Accurate Sequence Alignment with SNAP
Matei Zaharia, William J. Bolosky, Kristal Curtis +6
We present the Scalable Nucleotide Alignment Program (SNAP), a new short and long read aligner that is both more accurate (i.e., aligns more reads with fewer errors) and 10-100x fa…
Algorithms for Implicit Hitting Set Problems
Karthekeyan Chandrasekaran, Richard Karp, Erick Moreno-Centeno +1
A hitting set for a collection of sets is a set that has a non-empty intersection with each set in the collection; the hitting set problem is to find a hitting set of minimum cardi…
Comparing Pedigree Graphs
Bonnie Kirkpatrick, Yakir Reshef, Hilary Finucane +3
Pedigree graphs, or family trees, are typically constructed by an expensive process of examining genealogical records to determine which pairs of individuals are parent and child.…
Sorting and Selection in Posets
Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel +2
Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study a more general setting, in which some pairs…