6 citations · 33 across the 33 of their papers we have counts for
7 papers · 2 filters
A constructive algorithm for the LLL on permutations
David G. Harris, Aravind Srinivasan
While there has been significant progress on algorithmic aspects of the Lovász Local Lemma (LLL) in recent years, a noteworthy exception is when the LLL is used in the context of r…
Tighter inapproximability for set cover
David G. Harris
Set Cover is a classic NP-hard problem; as shown by Slavík (1997) the greedy algorithm gives an approximation ratio of . A series of works by Lund \& Yann…
Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovasz Local Lemma
David G. Harris
The Lopsided Lovász Local Lemma (LLLL) is a powerful probabilistic principle which has been used in a variety of combinatorial constructions. While originally a general statement a…
Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovasz Local Lemma
David G. Harris
Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low (almost-) independence. A series of pa…
Derandomized concentration bounds for polynomials, and hypergraph maximal independent set
David G. Harris
A parallel algorithm for maximal independent set (MIS) in hypergraphs has been a long-standing algorithmic challenge, dating back nearly 30 years to a survey of Karp & Ramachandran…
Distributed -Coloring in Sublogarithmic Rounds
David G. Harris, Johannes Schneider, Hsin-Hao Su
We give a new randomized distributed algorithm for -coloring in the LOCAL model, running in rounds in a graph of maximum degree…
Improved bounds and algorithms for graph cuts and network reliability
David G. Harris, Aravind Srinivasan
Karger (SIAM Journal on Computing, 1999) developed the first fully-polynomial approximation scheme to estimate the probability that a graph becomes disconnected, given that its…