6 citations · 33 across the 33 of their papers we have counts for
Showing 2019 · cs.DSShow all
3 papers · 2 filters
cs.DS2019★ 1 cited
Deterministic algorithms for the Lovasz Local Lemma: simpler, more general, and more parallel
David G. Harris
The Lovász Local Lemma (LLL) is a keystone principle in probability theory, guaranteeing the existence of configurations which avoid a collection of "bad" events which…
cs.DS2019
Algorithms for weighted independent transversals and strong colouring
Alessandra Graf, David G. Harris, Penny Haxell
An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are k…
cs.DS2019
Exponentially Faster Massively Parallel Maximal Matching
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, however, we still have a far…