6 citations · 33 across the 33 of their papers we have counts for
11 papers · 1 filter
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…
New bounds for the Moser-Tardos distribution
David G. Harris
The Lovasz Local Lemma (LLL) is a probabilistic tool which has been used to show the existence of a variety of combinatorial structures with good "local" properties. The "LLL-distr…
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…
Comparison of two convergence criteria for the variable-assignment Lopsided Lovasz Local Lemma
David G. Harris
The Lopsided Lovasz Local Lemma (LLLL) is a cornerstone probabilistic tool for showing that it is possible to avoid a collection of "bad" events as long as their probabilities and…
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…
Tight bounds and conjectures for the isolation lemma
Vance Faber, David G. Harris
Given a hypergraph and a weight function on its vertices, we say that is isolating if there is exactly one edge of minimum weight $w(e) =…
Some results on chromatic number as a function of triangle count
David G. Harris
A variety of powerful extremal results have been shown for the chromatic number of triangle-free graphs. Three noteworthy bounds are in terms of the number of vertices, edges, and…
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…