PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE
LOVÁSZ LOCAL LEMMA VIA WITNESS DAGS

arXiv:1509.06430v7 [cs.DM] 28 Sep 2017

BERNHARD HAEUPLER1 AND DAVID G. HARRIS2

Abstract. The Lovász Local Lemma (LLL) is a cornerstone principle in the probabilistic method
of combinatorics, and a seminal algorithm of Moser & Tardos (2010) provides an efficient randomized
algorithm to implement it. This can be parallelized to give an algorithm that uses polynomially
many processors and runs in O(log 3 n) time on an EREW PRAM, stemming from O(log n) adaptive
computations of a maximal independent set (MIS). Chung et al. (2014) developed faster local
and parallel algorithms, potentially running in time O(log 2 n), but these algorithms require more
stringent conditions than the LLL.
We give a new parallel algorithm that works under essentially the same conditions as the original
algorithm of Moser & Tardos but uses only a single MIS computation, thus running in O(log 2 n)
time on an EREW PRAM. This can be derandomized to give an NC algorithm running in time
O(log 2 n) as well, speeding up a previous NC LLL algorithm of Chandrasekaran et al. (2013).
We also provide improved and tighter bounds on the run-times of the sequential and parallel
resampling-based algorithms originally developed by Moser & Tardos. These apply to any problem
instance in which the tighter Shearer LLL criterion is satisfied.

1. Introduction
The Lovász Local Lemma (LLL), first introduced in [5], is a cornerstone principle in probability
theory. In its simplest symmetric form, it states that if one has a probability space Ω and a set of
m “bad” events B in that space, and each such event has probability PΩ (B) ≤ p; and each event
depends on at most d events (including itself), then under the criterion
(1)

epd ≤ 1

there is a positive probability that no bad events occurs. If equation (1) holds, we say the symmetric
LLL criterion is satisfied.
Although the LLL applies to general probability spaces, and the notion of dependency for a
general space can be complicated, most applications in combinatorics use a simpler setting in
which the probability space Ω is determined by a series of discrete variables X1 , . . . , Xn , each of
which is drawn independently with PΩ (Xi = j) = pij . Each bad event B ∈ B is a Boolean function
of a subset of variables SB ⊆ [n]. Then events B, B ′ are dependent (denoted B ∼ B ′ ) if they share
a common variable, i.e., SB ∩ SB ′ 6= ∅; note that B ∼ B. We say a set of bad events I ⊆ B is
independent if B 6∼ B ′ for all distinct pairs B, B ′ ∈ I. We say a variable assignment X avoids B if
every B ∈ B is false on X.
There is a more general form of the LLL, known as the asymmetric LLL, which can be stated
as follows. Suppose that there is a weighting function x : B → (0, 1) with the following property:
Y
(2)
∀B ∈ B
PΩ (B) ≤ x(B)
(1 − x(A))
A∼B
A6=B

1

School of Computer Science, Carnegie Mellon University. Research supported in part by NSF Awards CCF1527110 and CCF-1618280. Email: haeupler@cs.cmu.edu.
2
Department of Computer Science, University of Maryland, College Park, MD 20742. Research supported in part
by NSF Awards CNS-1010789 and CCF-1422569. Email: davidgharris29@gmail.com.
1

2

BERNHARD HAEUPLER AND DAVID G. HARRIS

then there is a positive probability of avoiding all bad events. The symmetric LLL is a special case
of this, derived by setting x(B) = ep. Both of these criteria are special cases of a yet more powerful
criterion, known as the Shearer criterion. This criterion requires a number of definitions to state;
we discuss this further in Section 1.3.
The probability of avoiding all bad events, while non-zero, is usually exponentially small; so the
LLL does not directly lead to efficient algorithms. Moser & Tardos [17] introduced a remarkable
randomized procedure, which we refer to as the Resampling Algorithm, which gives polynomial-time
algorithms for nearly all LLL applications:
Algorithm 1 The sequential Resampling Algorithm
1: Draw all variables X ∼ Ω.
2: while some bad events are true do
3:
Choose some true B ∈ B arbitrarily.
4:
Resample the variables in SB , independently from the distribution Ω.
This resampling algorithm terminates with probability one under the same condition as the
probabilistic LLL, viz. satisfying the Shearer criterion. The expected number of resamplings is
typically polynomial in the input parameters.
We note that this procedure can be useful even when the total number of bad events is exponentially large. At any stage of this algorithm, the expected number of bad events which are currently
true (and thus need to be processed), is still polynomial. If we have a subroutine which lists the
currently-true bad events in time poly(n), then the overall run-time of this algorithm can still be
polynomial in n. We refer to such a subroutine as a Bad-Event Checker. These are typically very
problem-specific; see [9] for more details.
1.1. Parallel algorithms for the LLL. Moser & Tardos also gave a simple RNC algorithm for
the LLL, shown below as Algorithm 2. Unlike their sequential algorithm, this requires a small slack
in the LLL criterion. In the symmetric setting, this criterion is
epd(1 + ǫ) ≤ 1

and in the asymmetric setting, it is given by
∀B ∈ B

(1 + ǫ)PΩ (B) ≤ x(B)

Y

A∼B
A6=B

(1 − x(A))

for some parameter ǫ ∈ (0, 1/2). We refer to these stronger criteria as ǫ-slack.
Algorithm 2 The Parallel Resampling Algorithm
1: Draw all variables X ∼ Ω.
2: while some bad events are true do
3:
Choose a maximal independent set I ofSbad events which are currently true.
4:
Resample, in parallel, all the variables B∈I SB from the distribution Ω.

P
x(B) 
) rounds
Moser & Tardos showed that this algorithm terminates after O ǫ−1 log(n B∈B 1−x(B)
1
with high probability. In each round, there are two main computational tasks: one must execute
a parallel Bad-Event Checker and one must find a maximal independent set (MIS) among the bad
events which are currently true.
Both of these tasks can be implemented in parallel models of computation. The most natural
complexity parameter in these settings is the number of variables n, since the final output of the
1We say that an event occurs with high probability (abbreviated whp), if it occurs with probability ≥ 1 − n−Ω(1) .

PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE LLL VIA WITNESS DAGS

3

algorithm (i.e. a satisfying solution) will require at least n bits. This paper will focus on the
PRAM (Parallel Random Access Machine) model, in which we are allowed poly(n) processors and
polylog(n) time. There are a number of variants of the PRAM model, which differ in (among other
things) the ability and semantics of multiple processors writing simultaneously to the same memory
cell. Two important cases are the CRCW model, in which multiple cells can simultaneously write
(the same value) to a cell, and the EREW model, in which each memory cell can only be used by a
single processor at a time. Nearly all “housekeeping” operations (sorting and searching lists, etc.)
can also be implemented in O(log n) time using standard techniques in either model.
A Bad-Event Checker can typically be implemented in time O(log n). The step of finding an
MIS can potentially become a computational bottleneck. In [15], Luby introduced randomized
algorithms for computing the MIS of a graph G = (V, E) using poly(|V |) processors; in the CRCW
model of computation, this algorithm requires time O(log |V |) while in other models such as EREW
it requires time O(log2 |V |). Luby also discussed a deterministic algorithm using O(log2 |V |) time
(in either model).
Applying Luby’s MIS algorithm to the Resampling Algorithm yields an overall run-time of
P
P
x(B)
x(B)
)) (on EREW) or O(ǫ−1 log2 (n B∈B 1−x(B)
)) (on CRCW) and the overO(ǫ−1 log3 (n B∈B 1−x(B)
P
x(B)
all processor complexity is poly(n, B∈B 1−x(B) )).2
The computation of an MIS is relatively costly. In [4], Chung et al. gave several alternative
algorithms for the symmetric LLL which either avoid this step or reduce its cost. One algorithm,
based on bad events choosing random priorities and resampling a bad event if it has earlier priority
than its neighbors, runs in O(ǫ−1 log m) distributed rounds. This can be converted to a PRAM
algorithm using O(ǫ−1 log2 m) time (in EREW) and O(ǫ−1 log m) time (in CRCW). Unfortunately,
this algorithm requires a stronger criterion than the LLL: namely, in the symmetric setting, it
requires that epd2 ≤ (1 − ǫ). In many applications of the LLL, particularly those based on Chernoff
bounds for the sum of independent random variables, this stricter criterion leads to qualitatively
similar results as the symmetric LLL. In other cases, this loses much critical precision leading to
weaker results. In particular, their bound essentially corresponds to the state of the art [16] before
the break-through results of Moser and Moser & Tardos [16, 17].
Another parallel algorithm of Chung et al. requires only the standard symmetric LLL criterion
and runs in O(ǫ−1 (log2 d)(log m)) rounds, subsequently reduced to O(ǫ−1 (log d)(log m)) rounds by
[8]. When d is polynomial in m, these do not improve on the Moser-Tardos algorithm. More recent
distributed algorithms for the LLL such as [7] do not appear to lead to PRAM algorithms.
In [17], a deterministic parallel (NC) algorithm for the LLL was given, under the assumption
that d = O(1). This was strengthened in [3] to allow arbitrary d under a stronger LLL criterion
epd1+ǫ ≤ 1, with a complexity of O(ǫ−1 log3 (mn)) time and (mn)O(1/ǫ) processors (in either CRCW
or EREW). This can be extended to an asymmetric setting, but there are many more technical
conditions on the precise form of B.
1.2. Overview of our results. In Section 2, we introduce a new theoretical structure to analyze
the behavior of the Resampling Algorithm, which we refer to as the witness DAG. This provides
an explanation or history for some or all of the resamplings that occur. This generalizes the notion
of a witness tree, introduced by Moser & Tardos in [17], which only provides the history of a single
resampling. We use this tool to show stronger bounds on the Parallel Resampling Algorithm given
by Moser & Tardos:
Theorem 1.1. Suppose that the Shearer criterion is satisfied with ǫ-slack. Then whp the Parallel
Resampling Algorithm terminates after O(ǫ−1 log n) rounds.
2The weighting function x(B) plays a somewhat mysterious role in the LLL, and it can be confusing to have it
appear in the complexity bounds for Resampling Algorithm. In most (although not all) applications, the expression
P
x(B)
B∈B 1−x(B) ) can be bounded as poly(n).

4

BERNHARD HAEUPLER AND DAVID G. HARRIS

Suppose furthermore we have a Bad-Event Checker which uses polynomial processors and T
time. Then the total complexity of the Parallel Resampling Algorithm is ǫ−1 nO(1) processors, and
2
O( (log n)(Tǫ+log n) ) time (in EREW model) or O( (log n)(Tǫ +log n) ) time (in CRCW model).
These bounds are independent of the LLL weighting function x(B) and the number of bad events
m. These simplify similar bounds shown in Kolipaka & Szegedy [14], which show that Parallel
Resampling Algorithm terminates, with constant probability, after O(ǫ−1 log(n/ǫ)) rounds.3
In Sections 3 and 4, we develop a new parallel algorithm for the LLL. The basic idea of this
algorithm is to select a random resampling table and then precompute all possible resamplingpaths compatible with it. Surprisingly, this larger collection, which in a sense represents all possible
trajectories of the Resampling Algorithm, can still be computed relatively quickly (in approximately
O(ǫ−1 log2 n) time). Next, we find a single MIS of this larger collection, which determines the
complete set of resamplings. It is this reduction from ǫ−1 log n separate MIS algorithms to just one
that is the key to our improved run-time.
We will later analyze this parallel algorithm in terms of the Shearer criterion, but this requires
many preliminary definitions. We give a simpler statement of our new algorithm for the symmetric
LLL criterion:
Theorem 1.2. Suppose that we have a Bad-Event Checker using O(log mn) time and poly(m, n)
processors. Suppose that each bad event B has PΩ (B) ≤ p and is dependent with at most d bad
events and that epd(1 + ǫ) ≤ 1 for some ǫ > 0. Then, there is an EREW PRAM algorithm to find
a configuration avoiding B whp using Õ(ǫ−1 log(mn) log n) time and poly(m, n) processors.4
In Section 5, we derandomize this algorithm under a slightly more stringent LLL criterion. The
full statement of the result is somewhat complex, but a summary is that if epd1+ǫ < 1 then we
obtain a deterministic EREW algorithm using O(ǫ−1 log2 (mn)) time and (mn)O(1/ǫ) processors.
This is NC for constant ǫ > 0.
The following table summarizes previous and new parallel run-time bounds for the LLL. For
simplicity, we state the symmetric form of the LLL criterion, although many of these algorithms
are compatible with asymmetric LLL criteria as well. The run-time bounds are simplified for
readability, omitting terms which are negligible in typical applications.
Model
LLL criterion
Reference
Run-time
Previous results
Randomized CRCW PRAM epd(1 + ǫ) ≤ 1
[17]
ǫ−1 log2 m
Randomized EREW PRAM epd(1 + ǫ) ≤ 1
[17]
ǫ−1 log3 m
1+ǫ
Deterministic EREW PRAM
epd
≤1
[3]
ǫ−1 log3 m
2
Randomized CRCW PRAM
epd ≤ 1 − ǫ
[4]
ǫ−1 log m
Randomized EREW PRAM
epd2 ≤ 1 − ǫ
[4]
ǫ−1 log2 m
This paper
Randomized CRCW PRAM epd(1 + ǫ) ≤ 1 Resampling Algorithm ǫ−1 log2 n
Randomized EREW PRAM epd(1 + ǫ) ≤ 1 Resampling Algorithm ǫ−1 log3 n
Randomized EREW PRAM epd(1 + ǫ) ≤ 1
New algorithm
ǫ−1 log2 m
1+ǫ
Deterministic EREW PRAM
epd
≤1
New algorithm
ǫ−1 log2 m
Although the main focus of this paper is on parallel algorithms, our techniques also lead to a
new and stronger concentration result for the run-time of the sequential Resampling Algorithm.
The full statement appears in Section 6; we provide a summary here:
3Note that Kolipaka & Szegedy use m for the number of variables and n for the number of bad events, while we

do the opposite. In this paper, we have translated all of their results into our notation. The reader should be careful
to keep this in mind when reading their original paper.
4The Õ notation hides polylogarithmic factors, i.e. Õ(t) = t(log t)O(1) .

PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE LLL VIA WITNESS DAGS

5

Theorem 1.3. Suppose that the asymmetric LLL criterion is satisfied with ǫ-slack. Then whp the
P x(B)
2 
Resampling Algorithm performs O ( B 1−x(B)
) + logǫ n resamplings. Alternatively, suppose that
the symmetric LLL criterion epd ≤ 1 is satisfied. Then whp the Resampling Algorithm performs
O(n + d log2 n) resamplings.
Similar concentration bounds have been shown in [14] and [1]. The main technical innovation
P

x(B)
B

1−x(B)
), whereas the new concentration
here is that prior concentration bounds have the form O(
ǫ
bounds are largely independent of ǫ (as long as it is not too small).

1.3. Stronger LLL criteria. The LLL criterion, in either its symmetric or asymmetric form, depends on only two parameters: the probabilities of the bad events, and their dependency structure.
The symmetric LLL criterion epd ≤ 1 is a very simple criterion involving these parameters, but it
is not the most powerful. In [18], Shearer gave the strongest possible criterion that can be stated in
terms of these parameters alone. This criterion is somewhat cumbersome to state and difficult to
work with technically, but it is useful theoretically because it subsumes many of the other simpler
criteria.
We note that the “lopsided” form of the LLL can be applied to this setting, in which bad events
are atomic configurations of the variables (as in a k-SAT instance), and this can be stronger than
the ordinary LLL. As shown in [10], there are forms of lopsidependency in the Moser-Tardos setting
which can even go beyond the Shearer criterion itself. However, the Parallel Resampling Algorithm
does not work in this setting; alternate, slower, parallel algorithms which can take advantage of
this lopsidependency phenomenon are given in [10], [12]. In this paper we are only concerned with
the standard (not lopsided) LLL.
To state the Shearer criterion, it will be useful to suppose that the dependency structure of our
bad events B is fixed, but the probabilities for the bad events have not been specified. We define
the independent-set polynomial Q(I, p) as
X
Y
Q(I, p) =
p(B)
(−1)|J|−|I|
I⊆J⊆B
J independent

B∈J

for any I ⊆ B. Note that Q(I, p) = 0 if I is not an independent set. This quantity plays a key role
in Shearer’s criterion for the LLL [18] and the behavior of the Resampling Algorithm. We say that
the probabilities p satisfy the Shearer criterion iff Q(∅, p) > 0 and Q(I, p) ≥ 0 for all independent
sets I ⊆ B.
Proposition 1.4 ([18]). Suppose that p satisfies the Shearer criterion. Then any probability space
with the given dependency structure and probabilities PΩ = p has a positive probability that none of
the bad events B are true.
Suppose that p do not satisfy the Shearer criterion. Then there is a probability space Ω with the
given dependency structure and probabilities PΩ = p for which, with probability one, at least one
B ∈ B is true.
Proposition 1.5 ([18]). Suppose that p(B) ≤ p′ (B) for all B ∈ B. Then, if p′ satisfies the Shearer
criterion, so does p.
One useful parameter for us will be the following:
Definition 1.6. For any bad event B, define the measure of B to be µ(B) =

Q({B},PΩ )
Q(∅,PΩ ) .

In [14], Kolipaka & Szegedy showed that if the Shearer criterion is satisfied, then the Resampling
Algorithm terminates with probability one; furthermore, the run-time of the Resampling Algorithms
can be bounded in terms of the measures µ.
Proposition 1.7 ([14]). The expected number of resamplings of any B ∈ B is at most µ(B).

6

BERNHARD HAEUPLER AND DAVID G. HARRIS

P
This leads us to define the work parameter for the LLL by W = B∈B µ(B). Roughly speaking,
the expected running time of the Resampling Algorithm is O(W ); we will later show (in Section 6)
that such a bound holds whp as well.
Although the sequential Resampling Algorithm can often work well when the Shearer criterion is
satisfied (almost) exactly, the Parallel Resampling Algorithm typically requires an additional small
slack.
Definition 1.8. We say that the Shearer criterion is satisfied with ǫ-slack, if the vector of probabilities (1 + ǫ)PΩ satisfies the Shearer criterion.
It it extremely difficult to directly show that the Shearer criterion is satisfied in a particular
instance. There are alternative criteria, which are weaker than the full Shearer criterion but much
easier to work with computationally. Perhaps the simplest is the asymmetric LLL criterion. The
connection between the Shearer criterion and the asymmetric LLL criterion was shown by Kolipaka
& Szegedy in [14].
Theorem 1.9 ([14]). Suppose that a weighting function x : B → (0, 1) satisfies
Y
∀B ∈ B
PΩ (B)(1 + ǫ) ≤ x(B)
(1 − x(A))
A∼B
A6=B

Then the Shearer criterion is satisfied with ǫ-slack, and µ(B) ≤

x(B)
1−x(B)

for all B ∈ B.

This was extended to the cluster-expansion LLL criterion of [2] by Harvey & Vondrák in [13]:
Theorem 1.10 ([13]). For any bad event B, let N (B) denote the set of bad events A with A ∼ B.
Suppose that a weighting function µ̃ : B → [0, ∞) satisfies
Y
X
µ̃(A)
∀B ∈ B
µ̃(B) ≥ PΩ (B)(1 + ǫ)
I⊆N (B) A∈I
I independent

Then the Shearer criterion is satisfied with ǫ-slack, and µ(B) ≤ µ̃(B) for all B ∈ B.
For the remainder of this paper, we will assume unless stated otherwise that our probability
space Ω satisfies the Shearer criterion with ǫ-slack. We will occasionally derive certain results for
the symmetric LLL criterion as a corollary of results on the full Shearer criterion.
2. The witness DAG and related structures
There are two key analytical tools introduced by Moser & Tardos to analyze their algorithm:
the resampling table and witness tree.
The resampling table R is a table of values R(i, t), where i ranges over the variables 1, . . . , n
and t ranges over the positive natural numbers. Each cell R(i, t) is drawn independently from the
distribution of variable Xi , that is, R(i, t) = j with probability pij , independently of all other cells.
The intent of this table is that, instead of choosing new values for the variables in “on-line” fashion,
we precompute the future values of all the variables. The first entry in the table R(i, 1), is the
initial value for the variable Xi ; on the tth resampling, we set Xi = R(i, t + 1).5
The witness tree is a structure which records the history of all variables involved in a given
resampling. Moser & Tardos give a very clear and detailed description of the process for forming
witness trees; we provide a simplified description here. Suppose that the Resampling Algorithm
resample bad events B1 , . . . , Bt in order (the algorithm has not necessarily terminated by this
point). We build a witness-tree τ̂t for the tth resampling, as follows. We place a node labeled by
5Although nominally the resampling table provides a countably infinite stream of values for each variable, in
practice we will only need to use approximately ǫ−1 log n distinct values for each variable.

PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE LLL VIA WITNESS DAGS

7

Bt at the root of the tree. We then go backwards in time for j = t − 1, . . . , 1. For each Bj , if there
is a node v ′ in the tree labeled by B ′ ∼ Bj , then we add a new node v labeled by Bj as a child
of v ′ ; if there are multiple choices of v ′ , we always select the one of greatest depth (breaking ties
arbitrarily.) If there is no such node v ′ , then we do not add any nodes to the tree for that value of
j.
2.1. The witness DAG. The witness tree τ̂t only provides an explanation for the single resampling
at time t; it may discard information about other resamplings. We now consider a related object,
the witness DAG (abbreviated WD ) that can record information about multiple resamplings, or
all of the resamplings.
A WD is a directed acyclic graph, whose nodes are labeled by bad events. For nodes v, v ′ ∈ G,
we write v ≺ v ′ if there is an edge from v to v ′ . We impose two additional requirements, which we
refer to as the comparability conditions. First, if nodes v, v ′ are labeled by B, B ′ and B ∼ B ′ , then
either v ≺ v ′ or v ′ ≺ v; second, if B 6∼ B ′ then there is no edge between v, v ′ .
We let |G| denote the number of vertices in a WD G.
It is possible that a WD can contain multiple nodes with the same label. However, because of the
comparability conditions, all such nodes are linearly ordered by ≺. Thus for any WD G and any
B ∈ B, the nodes of G labeled B can be unambiguously sorted. Accordingly, we use the notation
(B, k) for the kth node of G labeled by B. For any node v, we refer to this ordered pair (B, k)
as the extended label of v. Every node in a WD receives a distinct extended label. We emphasize
that this is a notational convenience, as an extended label of a node can be recovered from the WD
along with its original labels.
Given a full execution of the Resampling Algorithm, there is a particularly important WD which
we refer to as the Full Witness DAG Ĝ (abbreviated FWD ). We construct this as follows. Suppose
that we resample bad events B1 , . . . , Bt . Then Ĝ has vertices v1 , . . . , vt which are labeled B1 , . . . , Bt .
We place an edge from vi to vj iff i < j and Bi ∼ Bj . We emphasize that Ĝ is a random variable.
The FWD (under different terminology) was analyzed by Kolipaka & Szegedy in [14], and we will
use their results in numerous places. However, we will also consider partial WDs, which record
information about only a subset of the resamplings.
As witness trees and single-sink WDs are closely related, we will often use the notation τ for a
single-sink WD. We let Γ denote the set of all single-sink WDs, and for any B ∈ B we let Γ(B)
denote the set of single-sink WDs whose sink node is labeled B.
2.2. Compatibility conditions for witness DAGs and resampling tables. The MoserTardos proof hinged upon a method for converting an execution log into a witness tree, and
necessary conditions were given for a witness tree being produced in this fashion in terms of its
consistency with the resampling table. We will instead use these conditions as a definition of
compatibility.
Definition 2.1 (Path of a variable). Let G be a WD. For any i ∈ [n], let G[i] denote the subgraph
of G induced on all vertices v labeled by B with i ∈ SB . Because of the comparability conditions,
G[i] is linearly ordered by ≺; thus we refer to G[i] as the path of variable i.
Definition 2.2 (Configuration of v). Let G be a WD and R a resampling table. Let v ∈ G be
labeled by B. For each i ∈ SB , let yv,i denote the number of vertices w ∈ G[i] such that w ≺ v.
We now define the configuration of v by
v
XG
(i) = R(i, 1 + yv,i )

Definition 2.3 (Compatibility of WD G with resampling table R). For a WD G and a resampling
table R, we say that G is compatible with R if, for all nodes v ∈ G labeled by B ∈ B, it is the case
v . This is well-defined because X v assigns values to all the
that B is true on the configuration XG
G
variables in SB .

8

BERNHARD HAEUPLER AND DAVID G. HARRIS

We define ΓR to be the set of single-sink WDs compatible with R, and similarly for ΓR (B).
The following are key results used by Moser & Tardos to bound the running time of their
resampling algorithm:
Definition 2.4 (Weight of a WD). Let G be any WD,
Q whose nodes are labeled by bad events
B1 , . . . , Bs . We define the weight of G to be w(G) = sk=1 PΩ (Bk ).

Proposition 2.5. For a random resampling table R, any WD G has probability w(G) of being
compatible with R.
v follows the law of Ω, and so the probability that B is
Proof. For any node v ∈ G, note that XG
v
true of the configuration XG is PΩ (B). Next, note that each node v ∈ G imposes conditions on
disjoint sets of entries of R, and so these events are independent.


Proposition 2.6. Suppose we run the Resampling Algorithm, taking values for the variables from
the resampling table R. Then Ĝ is compatible with R.
Proof. Suppose there is a node v ∈ Ĝ with extended label (B, k). Thus, B must be resampled at
least k times. Suppose that the kth resampling occurs at time t. Let Y be the configuration at time
v (i) for all i ∈ S . For, the graph Ĝ must
t, just before this resampling. We claim that Y (i) = XĜ
B
contain all the resamplings involving variable i. All such nodes would be connected to vertex v (as
they overlap in variable i), and those that occur before time t are precisely those with an edge to v.
So yv,i is exactly the number of bad events up to time t that involve variable i. Thus, just before
v (i),
the resampling at time t, variable i was on its 1 + yv,i resampling. So Y (i) = R(i, 1 + yv,i ) = XĜ
as claimed.
In order for B to be resampled at time t, it must have been the case that B was true, i.e., that
v on S , necessarily B holds on configuration
B held on configuration Y . Since Y agrees with XĜ
B
v

XĜ as well. This is true for all v ∈ G and so G is compatible with R.
2.3. Prefixes of a WD. A WD records information about many resamplings. If we are only
interested in the history of a subset of its nodes, then we can form a prefix subgraph which discards
irrelevant information.
Definition 2.7 (Prefix graph). For any WD G and vertices v1 , . . . , vℓ ∈ G, let G(v1 , . . . , vℓ ) denote
the subgraph of G induced on all vertices which have a path to at least one of v1 , . . . , vℓ .
If H is a subgraph of G with H = G(v1 , . . . , vℓ ) for some v1 , . . . , vℓ ∈ G, then we say that H is
a prefix of G.
Using Definition 2.7, we can give a more compact definition of the configuration of a node:
v (i) = R(i, |G(v)[i]|).
Proposition 2.8. For any WD G and v ∈ G, we have XG

Proof. Suppose that v is labeled by B. The graph G(v)[i] contains precisely v itself and the other
nodes w ∈ G[i] with w ≺ v. So |G(v)[i]| = yv,i + 1.


Proposition 2.9. Suppose G is compatible with R and H is a prefix of G. Then H is compatible
with R.

Proof. Let H = G(v1 , . . . , vℓ ). Consider w ∈ H labeled by B. We claim that H(w) = G(w). For,
consider any u ∈ H(w). So u has a path to w in H; it also must have a path to w in G. On the
other hand, suppose u ∈ G(w), so u has a path p to w in G. As w has a path to one of v1 , . . . , vℓ ,
this implies that every vertex in the path p also has such a path. Thus, the path p is in H, and
hence u has a path in H to w, so u ∈ H(w).
Next, observe that for any i ∈ SB we have
w
w
XG
(i) = R(i, |G(w)[i]|) = R(i, |H(w)[i]|) = XH
(i)

w.
and by hypothesis, B is true on XG



PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE LLL VIA WITNESS DAGS

9

2.4. Counting witness trees and WDs. In this section, we bound the summed weights of
certain classes of WDs. In light of Proposition 2.5, this will upper-bound the expected number of
resamplings.
Proposition 2.10 ([14]). For any B ∈ B, we have
X
w(τ ) ≤ µ(B).
τ ∈Γ(B)

Proof. For any WD G with a single sink node v labeled B, we define Ij′ for non-negative integers
′
j using the following recursion. I0′ = {v}, and Ij+1
is the set of vertices in G whose out-neighbors
′
′
all lie in I0 ∪ · · · ∪ Ij . Let Ij denote the labels of the vertices in Ij′ ; so I0 = {B}.
Now observe that by the comparability conditions each set Ij is an independent set, and for each
B ′ ∈ Ij+1 there is some B ′′ ∼ B ′ , B ′′ ∈ Ij . Also, the mapping from G to I0 , . . . , Ij is injective. We
thus may sum over all such I1 , . . . , I∞ to obtain an upper bound on the weight of such WDs. In
[14] Theorem 14, this sum is shown to be Q({B}, PΩ )/Q(∅, PΩ ) (although their notation is slightly
different.)

We will now take advantage of the ǫ-slack in our probabilities.
Proposition 2.11. Given any V ⊆ B, we say that V is a dependency-clique if B ∼ B ′ for all
B, B ′ ∈ V . If V is a dependency-clique then for any ρ ∈ [0, ǫ) we have
X Q({B}, (1 + ρ)PΩ )
1+ρ
≤
.
Q(∅, (1 + ρ)PΩ )
ǫ−ρ
B∈V

Proof. Consider the probability vector p defined by
(
(1 + ǫ)PΩ (B) if B ∈ V
p(B) =
(1 + ρ)PΩ (B) if B ∈
/V

Since V is a clique, any independent set I has |I ∩ V | ≤ 1. Thus we calculate Q(∅, p) as
Y
Y
X
X
ǫ−ρ
)PΩ (A)
(1 + [A ∈ V ]
p(A) =
Q(∅, p) =
(−1)|I|
(−1)|I|
1+ρ
A∈I

I⊆B
I independent

=

X

(−1)|I| (1 + [I ∩ V 6= ∅]

X

(−1)|I|

I⊆B
I independent

=

I⊆B
I independent

= Q(∅, (1 + ρ)PΩ ) −

Y

A∈I

I⊆B
I independent

ǫ−ρ Y
)
(1 + ρ)PΩ (A)
1+ρ

(1 + ρ)PΩ (A) +

A∈I

ǫ−ρ X
1+ρ
B∈V

A∈I

X

I⊆B
I independent
I∩V ={B}

(−1)|I|

Y

(1 + ρ)PΩ (A)

A∈I

(ǫ − ρ) X
Q({B}, (1 + ρ)PΩ )
1+ρ
B∈V

We use here the Iverson notation so that [I ∩ V 6= ∅] is one if I ∩ V 6= ∅ and zero otherwise.
Note that p ≤ (1 + ǫ)PΩ and so by Propositions 1.4 and 1.5 we have Q(∅, p) > 0 and Q({B}, (1 +
ρ)PΩ ) ≥ 0 for all B ∈ V . Thus,
P
X Q({B}, (1 + ρ)PΩ )
B∈V Q({B}, (1 + ρ)PΩ )
=
P
Q(∅, (1 + ρ)PΩ )
Q(∅, p) + (ǫ−ρ)
B∈V
B∈V Q({B}, (1 + ρ)PΩ )
1+ρ
P
Q({B}, (1 + ρ)PΩ )
1+ρ
=
≤ (ǫ−ρ) B∈V
P
ǫ−ρ
Q({B}, (1 + ρ)PΩ )
1+ρ

B∈V

10

BERNHARD HAEUPLER AND DAVID G. HARRIS


Definition 2.12 (Adjusted weight). For any WD G, we define the adjusted weight with respect
to rate factor ρ by
aρ (G) = w(G)(1 + ρ)|G| .
Observe that w(G) = a0 (G).
Corollary 2.13. Suppose that V ⊆ B is a dependency-clique. Then for any ρ ∈ [0, ǫ) we have
X
1+ρ
aρ (B) ≤
.
ǫ−ρ
B∈V

Proof. Applying Proposition 2.10 using the probability vector p = (1 + ρ)PΩ gives
X X
X Q({B}, (1 + ρ)PΩ )
aρ (B) ≤
Q(∅, (1 + ρ)PΩ )
B∈V τ ∈Γ(B)

B∈V

Now apply Proposition 2.11.



Corollary 2.14. We have the bound W ≤ n/ǫ, where we recall the definition W =
Proof. We write
W =

X

B∈B

µ(B) =

P

B∈B

µ(B).

X Q({B}, PΩ )
X X Q({B}, PΩ )
≤
Q(∅, PΩ )
Q(∅, PΩ )
i∈[n] B:SB ∋i

B∈B

Now note that for any i ∈ [n], the set of bad events B with i ∈ SB forms a dependency-clique.
P
1
Ω)
Thus, applying Proposition 2.11 with ρ = 0 gives i∈SB Q({B},P

Q(∅,PΩ ) ≤ ǫ .
Corollary 2.15 ([14]). The total weight of all single-sink WDs is at most n/ǫ.

Proof. Follows immediately from Proposition 2.10 and Corollary 2.14.



Proposition 2.16. For r ≥ 1 + 1/ǫ, the expected number of single-sink WDs compatible with R
containing more than r nodes is at most enr(1 + ǫ)−r
Proof. For any ρ ∈ [0, ǫ), sum over such WDs to obtain:
X
X
X
X
aρ (τ )
w(τ )(1 + ρ)|τ | = (1 + ρ)−r
w(τ ) ≤ (1 + ρ)−r
P (τ compatible with R) =
τ ∈Γ
|τ |≥r

≤ (1 + ρ)−r

τ ∈Γ
|τ |≥r

τ ∈Γ
|τ |≥r

τ ∈Γ
|τ |≥r

X X

X

aρ (τ )

i∈[n] B:SB ∋i τ ∈Γ(B)

≤ (1 + ρ)−r n

1+ρ
ǫ−ρ

by Corollary 2.13

Now take ρ = ǫ−(1+ǫ)/r. By our condition r ≥ 1+1/ǫ we have ρ ∈ [0, ǫ) and so Proposition 2.11
nr r
applies. Hence the expected number of such WDs is thus at most (r−1)r−1
≤ enr(1 + ǫ)−r . 
(1+ǫ)r
) nodes. Whp all but
Corollary 2.17. Whp, every element of ΓR contains O( log(n/ǫ)
ǫ
10 log n
R
of Γ contain at most
nodes.
ǫ
Proof. This follows immediately from Markov’s inequality and Proposition 2.16.
Corollary 2.18. Whp, all WDs compatible with R have height O( logǫ n ).

10 log n
ǫ

elements


PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE LLL VIA WITNESS DAGS

11

Proof. Suppose that there is a WD G of height T compatible with R. Then for i = 1, . . . , T there
is a single-sink WD of height i compatible with R (take the graph G(v), where v is a node of height
i.) This implies that there Ω(T ) members of ΓR of height Ω(T ). By Proposition 2.17, this implies

T = O( logǫ n ).
Corollary 2.18 leads to a better bound on the complexity of the Parallel Resampling Algorithm.
The following Proposition 2.19 is remarkable in that the complexity is phrased solely in terms of
the number of variables n and the slack ǫ, and is otherwise independent of B.
Proposition 2.19. Suppose that the Shearer criterion is satisfied with ǫ-slack. Then whp the
Parallel Resampling Algorithm terminates after O( logǫ n ) rounds.
Suppose we have a Bad-Event Checker in time T and polynomial processors. Then the Parallel Resampling Algorithm can be executed using nO(1) /ǫ processors with an expected run-time of
2
O( (log n)(Tǫ+log n) ) (in the EREW model) or O( (log n)(Tǫ +log n) ) (in the CRCW model).
Proof. An induction on i shows that if the Parallel Resampling Algorithm runs for i steps, then Ĝ
has depth i, and it is compatible with R. By Corollary 2.18 whp this implies that i = O( logǫ n ).
n
This implies that the total time needed to identify true bad events is O(iT ) ≤ O( T log
ǫ ).
We next compute the time required for MIS calculations. We only show the calculation for the
EREW model, as the CRCW bound is nearly identical. Suppose that at stage i the number of
bad events which
P are currently true is vi . Then the total time spent calculating MIS, over the full
algorithm, is ti=1 O(log2 vi ).
P
Since log x is a concave-down function of x, this sum is at most O(t log2 ( vi /t)). On the other
hand, for each bad event which is at true at eachPstage, one
P can construct a distinct corresponding
single-sink WD compatible with R. Hence, E[ vi ] ≤ τ ∈Γ w(τ ) ≤ n/ǫ. As t ≤ logǫ n , we have
P
E[t log2 ( vi /t)] ≤ ǫ−1 log3 n. This shows the bound on the time complexity of the algorithm.
The expected number of bad events which are ever true is at most the weight of all single-sink
WDs, which is at most W ≤ n/ǫ. By Markov’s inequality, whp the total number of bad events
which are ever true is bounded by nO(1) /ǫ. The processor bound follows from this observation. 
3. Mutual consistency of witness DAGs
In Section 2, we have seen conditions for WDs to be compatible with a given resampling table
R. In this section, we examine when a set of WDs can be mutually consistent, in the sense that
they could all be prefixes of some (unspecified) FWD.
Definition 3.1 (Consistency of G, G′ ). Let G, G′ be WDs. We say that G is consistent with G′
is, for all variables i, either G[i] is an initial segment of G′ [i] or G′ [i] is an initial segment of G[i],
both of these as labeled graphs. (Carefully note the position of the quantifiers: If n = 2 and G[1] is
an initial segment of G′ [1] and G′ [2] is an initial segment of G[2], then G, G′ are consistent.)
Let G be any set of WDs. We say that G is pairwise consistent if G, G′ are consistent with each
other for all G, G′ ∈ G.
Proposition 3.2. Suppose H1 , H2 are prefixes of G. Then H1 is consistent with H2 .
Proof. Observe that for any w1 ≺ w2 ∈ Hj , we must have w1 ∈ Hj as well. It follows that Hj [i] is
an initial segment of G[i] for any i ∈ [n]. As both H1 [i] and H2 [i] are initial segments of G[i], one
of them must be an initial segment of the other.

Definition 3.3 (Merge of two consistent WDs). Let G, G′ be consistent WDs. Then we define the
merge G ∨ G′ as follows. If either G or G′ has a node v with an extended label (B, k), then we
create a corresponding node w ∈ G ∨ G′ labeled by B. We refer to the corresponding label of w as
(B, k).

12

BERNHARD HAEUPLER AND DAVID G. HARRIS

Now, let v1 , v2 ∈ G ∨ G′ have corresponding label (B1 , k1 ) and (B2 , k2 ). We create an edge
from v1 to v2 if either G or G′ has an edge between vertices with extended label (B1 , k1 ), (B2 , k2 )
respectively.
Note that for every vertex v ∈ G with extended label (B, k), there is a vertex in G ∨ G′ with
corresponding label (B, k); we will abuse notation slightly and use v to refer this vertex in G ∨ G′
as well.
Proposition 3.4. Let G, G′ be consistent WDs and let H = G ∨ G′ . If there is a path v1 , . . . , vℓ in
H and vℓ ∈ G, then also v1 , . . . , vℓ ∈ G.

Proof. Suppose that this path has corresponding labels (B1 , k1 ), . . . , (Bℓ , kℓ ). Let i ≤ ℓ be minimal
such that vi , . . . , vℓ are all in G. (This is well-defined as vℓ ∈ G). If i = 1 we are done.
Otherwise, we have vi ∈ G, vi−1 ∈ G′ − G. Note that Bi−1 ∼ Bi , so let j ∈ SBi−1 ∩ SBi . Note
that vi ∈ G[j], vi−1 ∈ G′ [j]. But observe that in H there is an edge from vi−1 to vi . As vi−1 ∈
/ G,
this edge must have been present in G′ . So G′ [j] contains the vertices vi−1 , vi , in that order, while
G[j] contains only the vertex vi . Thus, neither G[j] or G′ [j] can be an initial segment of the other.
This contradicts the hypothesis.

Proposition 3.5. Let G, G′ be consistent WDs and let H = G ∨ G′ . Then H is a WD and both G
and G′ are prefixes of it.
Proof. Suppose that H contains a cycle v1 , . . . , vℓ , v1 , and suppose v1 ∈ G. Then by Proposition 3.4
the cycle v1 , . . . , vℓ , v1 is present also in G, which is a contradiction.
Next, we show that the comparability conditions hold for H. Suppose that (B1 , k1 ) and (B2 , k2 )
are the corresponding labels of vertices in H, and B1 ∼ B2 . So let i ∈ SB1 ∩ SB2 . Without loss of
generality, suppose that G[i] is an initial segment of G′ [i]. So (B1 , k1 ) and (B2 , k2 ) appear in G′ [i].
Because of the comparability conditions for G′ , there is an edge in G′ on these vertices, and hence
there is an edge in H as well. On the other hand, if there is an edge in H between vertices (B1 , k1 )
and (B2 , k2 ), there must be such an edge in G or G′ as well; by the comparability conditions this
implies B1 ∼ B2 .
Finally, we claim that G = H(v1 , . . . , vℓ ) where v1 , . . . , vℓ are the vertices of G. It is clear that
G ⊆ H(v1 , . . . , vℓ ). Now, suppose w ∈ H(v1 , . . . , vℓ ). Then there is a path w, x1 , x2 , . . . , xk , v where
x1 , . . . , xk ∈ H and v ∈ G. By Proposition 3.4, this implies that w ∈ G.

Proposition 3.6. If v ∈ G ∨ G′ has corresponding label (B, k), then v also has extended label
(B, k).

Proof. Because of our rule for forming edges in G ∨ G′ , the only edges that can go to v from other
nodes labeled B, would have corresponding labels (B, ℓ) for ℓ < k. Thus, there are at most k − 1
nodes labeled B with an edge to v.
On the other hand, there must be nodes with extended label (B, k) in G or G′ ; say without loss
of generality the first. Then G must also have nodes with extended labels (B, 1), . . . , (B, k − 1).
These correspond to vertices w1 , . . . , wk−1 with corresponding labels (B, 1), . . . , (B, k − 1), all of
which have an edge to v. So there are at least k − 1 nodes labeled B with an edge to v.
Thus, G has exactly k − 1 nodes labeled B with an edge to v and hence v has extended label
(B, k).

Proposition 3.7. The operation ∨ is commutative and associative.

Proof. Commutativity is obvious from the symmetric way in which ∨ was defined. To show associativity, we can give the following symmetric characterization of H = (G1 ∨ G2 ) ∨ G3 : If G1 , G2
or G3 has a node labeled (B1 , k1 ) then so does H; there is an edge in H from (B1 , k1 ) to (B2 , k2 )
if there is such an edge in G1 , G2 or G3 .

Proposition 3.8. If G1 , G2 , G3 are pairwise consistent WDs, then G1 ∨ G2 is consistent with G3 .

PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE LLL VIA WITNESS DAGS

13

Proof. For any variable i ∈ [n], note that either G1 [i] is an initial segment of G2 [i] or vice-versa.
Also note that (G1 ∨ G2 )[i] is the longer of G1 [i] or G2 [i].
Now we claim that for any variable i, either G3 [i] is an initial segment of (G1 ∨G2 )[i] or vice-versa.
Suppose without loss of generality that G1 [i] is an initial segment of G2 [i]. Then (G1 ∨G2 )[i] = G1 [i].
By definition of consistency, either G1 [i] is an initial segment of G3 [i] or vice-versa. So (G1 ∨ G2 )[i]
is an initial segment of G3 [i] or vice-versa.

In light of Propositions 3.7 and 3.8, we can unambiguously define, for any pairwise consistent
set of WDs G = {G1 , . . . , Gℓ }, the merge
_
G = G1 ∨ G2 ∨ G3 · · · ∨ Gℓ

We can give another characterization of pairwise consistency, which is more illuminating although
less explicit:
Proposition 3.9. The WDs G1 , . . . , Gℓ are pairwise consistent iff there is some WD H such that
G1 , . . . , Gℓ are all prefixes of H.
Proof. For the forward direction: let H = G1 ∨ · · · ∨ Gl . By Proposition 3.5, each Gi is a prefix
of H. For the backward direction: by Proposition 2.10, any Gi1 , Gi2 are both prefixes of H, hence
consistent.

Proposition 3.10. Let G1 , G2 be consistent WDs and R a resampling table. Then G1 ∨ G2 is
compatible with R iff both G1 and G2 are compatible with R.
Proof. For the forward direction: let v ∈ G1 labeled by B. By Proposition 3.4, we have G1 (v) =
v =
(G1 ∨ G2 )(v). Thus for i ∈ SB we have |G1 (v)[i]| = |(G1 ∨ G2 )(v)[i]|. This implies that XG
1
v
v
v . As this is true for all v ∈ G , it
XG
. By hypothesis, B is true on XG
and hence XG
1
1 ∨G2
1 ∨G2
1
follows that G1 is compatible with R. Similarly, G2 is compatible with R.
For the backward direction: Let v ∈ G1 ∨ G2 . Suppose without loss of generality that v ∈ G1 .
v = Xv
As in the forward direction, we have XG
G1 ∨G2 ; by hypothesis B is true on the former so it is
1
true on the latter. Since this holds for all v ∈ G1 ∨ G2 , it follows that G1 ∨ G2 is compatible with
R.

4. A new parallel algorithm for the LLL
In this section, we will develop a parallel algorithm to enumerate the entire set ΓR . This will
allow us to enumerate (implicitly) all WDs compatible with R. In particular, we are able to simulate
all possible values for the FWD Ĝ, without running the Resampling Algorithm.
In a sense, both the Parallel Resampling Algorithm and our new parallel algorithm are building
up Ĝ. However, the Parallel Resampling Algorithm does this layer by layer, in an inherently
sequential way: it does not determine layer i + 1 until it has fixed a value for layer i, and resolving
each layer requires a separate MIS calculation.
Our new algorithm breaks this sequential bottleneck by exploring, in parallel, all possible values
for the computed MIS. Although this might seem like an exponential blowup, in fact we are able
to reduce this to a polynomial size by taking advantage of two phenomena: first, we can represent
the FWD in terms of single-sink WDs; second, a random resampling table drastically prunes the
space of compatible WDs.
4.1. Collectible witness DAGs. We will enumerate the set ΓR by building up its members nodeby-node. In order to do so, we must keep track of a slightly more general type of WDs, namely,
those derived by removing the root node from a single-sink WD. Such WDs have multiple sink
nodes, which are all at distance two in the dependency graph. The set of such WDs is larger than
ΓR , but still polynomially bounded.

14

BERNHARD HAEUPLER AND DAVID G. HARRIS

Definition 4.1 (Collectible WD). Suppose we are given a WD G, whose sink nodes are labeled
B1 , . . . , Bs . We say that G is collectible to B if B ∼ B1 , . . . , B ∼ Bs .
We say that G is collectible if it is collectible to some B ∈ B. Note that if G ∈ Γ(B) then G is
collectible to B. We use CWD as an abbreviation for collectible witness DAG.6
Proposition 4.2. Define
W′ =

X

B∈B

X
1
w(τ )
PΩ (B)
τ ∈Γ(B)

The expected total number of CWDs compatible with R is at most W ′ .
Proof. Suppose that G is a WD collectible to B. Then define G′ by adding to G a new sink node
labeled by B. As all the sink nodes in G are labeled by B ′ ∼ B, this G′ is a single-sink WD. Also,
w(G′ )
P (G compatible with R) = w(G) =
PΩ (B)
The total probability that there is some G compatible with R and collectible to B, is at most
the sum over all such G. Each WD G′ ∈ Γ(B) appears at most once in the sum and so
X X w(τ )
X
X
X
w(G′ )
≤
= W′
w(G) ≤
w(G) ≤
PΩ (B)
PΩ (B)
G collectible

B∈B
G collectible to B

B∈B
G collectible to B

B∈B τ ∈Γ(B)


Corollary 4.3. We have m ≤ W ′ ≤

P

µ(B)
B∈B PΩ (B) .

Proof. The upper bound
followsPfrom Proposition 2.10. For the lower bound, consider the contriP

bution to the sum B∈B PΩ1(B) τ ∈Γ(B) from the WDs τ with |τ | = 1.

The parameter W ′ , which dictates the run-time of our parallel algorithm, has a somewhat complicated behavior. For most applications of the LLL where the bad events are “balanced,” we have
W ′ ≈ m. Here are two examples of this.

Proposition 4.4. If the symmetric LLL criterion epd ≤ 1 is satisfied then W ′ ≤ me.
Proof. The asymmetric LLL criterion is satisfied by setting x(B) =
Theorem 1.9, we have µ(B) ≤ ePΩ (B) for all B ∈ B.

ePΩ (B)
1+ePΩ (B)

for all B ∈ B. By


Proposition 4.5. Let p : B → [0, 1] be a vector satisfying the two conditions:
(1) PΩ (B) ≤ p(B) for all B ∈ B
(2) p satisfies the Shearer criterion with ǫ-slack.
Then we have
(n/ǫ)
W′ ≤
minB∈B p(B)
Proof. For any WD G whose nodes are labeled B1 , . . . , Bs , define w′ (G) to be p(B1 ) · · · p(Bs ).
Now consider some τ ∈ Γ(B) which has s additional nodes labeled B1 , . . . , Bs . We have that
s
s
Y
Y
w′ (G)
w(G)
p(Bi ) =
PΩ (Bi ) ≤
=
.
PΩ (B)
p(B)
i=1

Thus, by Corollary 2.15,
X
W′ ≤

B∈B

i=1

P
X
(n/ǫ)
1
τ ∈Γ w(τ )
′
w (τ ) ≤
≤
.
p(B)
minB∈B p(B)
minB∈B p(B)
τ ∈Γ(B)

6This definition is close to the concept of partial witness trees introduced in [3].

PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE LLL VIA WITNESS DAGS

15


We note that Proposition 4.5 seems to say that W ′ becomes large when the probabilities p are
small. This seems strange, as bad events with small probability have a negligible effect. (For
instance, if a bad event has probability zero, we can simply ignore it.) A more accurate way to
read Proposition 4.5 is that W ′ becomes large only for problem instances which are close to the
Shearer bound and have small probabilities. Such instances would have some bad events with
simultaneously very low probability and very high dependency; in these cases then indeed W ′ can
become exponentially large.
4.2. Algorithmically enumerating witness DAGs. In the Moser-Tardos setting, the witness
trees were not actually part of the algorithm but were a theoretical device for analyzing it. Our new
algorithm is based on explicit enumeration of the CWDs. We will show that, for an appropriate
choice of parameter K, Algorithm 3 can be used to to enumerate all ΓR .
Algorithm 3 Enumerating witness DAGs
1: Randomly sample the resampling table R.
2: For each B ∈ B true in the initial configuration R(·, 1), create a graph with a single vertex
labeled B. We denote this initial set by F1 .
3: for k = 1, . . . , K do
4:
For each consistent pair G1 , G2 ∈ Fk , form G′ = G1 ∨G2 . If G′ is collectible and |G′ | ≤ k +1,
then add it to Fk+1 .
5:
For each G ∈ Fk which is collectible to B, create a new WD G′ by adding to G a new sink
node labeled B. If G′ is compatible with R then add it to Fk+1 .
Proposition 4.6. Let G ∈ Fk for any integer k ≥ 1. Then G is compatible with R.
Proof. We show this by induction on k. When k = 1, then G ∈ F1 is a singleton node v labeled by
v (i) = R(i, 1) for all i ∈ S , and so B is true on X v . So G is compatible with R.
B. Note that XG
B
G
Now for the induction step. First suppose G was formed by G = G1 ∨ G2 , for G1 , G2 ∈ Fk−1 . By
induction hypothesis, G1 , G2 are compatible with R. So by Proposition 3.8, G is compatible with
R. Second suppose G was formed in step (5), so by definition it must be compatible with R.

Proposition 4.7. If G is a CWD with at most k nodes and G is compatible with R, then G ∈ Fk .
Proof. We show this by induction on k. When k = 1, then G is a singleton node v labeled by B,
v (i) = R(i, 1). So B is true on the configuration R(·, 1), and so G ∈ F .
and XG
1
For the induction step, first note that if |G| < k, then by induction hypothesis G ∈ Fk−1 . So G
will be added to Fk in step (4) by taking G1 = G2 = G.
Next, suppose G has a single sink node v labeled by B. Consider the WD G′ = G − v. Note
that |G′ | = k − 1. Also, all the sink nodes in G′ must be labeled by some B ′ ∼ B (as otherwise
they would remain sink nodes in G). So G′ is collectible to B. By induction hypothesis, G′ ∈ Fk−1 .
Iteration k − 1 transforms the graph G′ ∈ Fk−1 into G (by adding a new sink node labeled by B),
and so G ∈ Fk as desired.
Finally, suppose that G has sink nodes v1 , . . . , vs labeled by B1 , . . . , Bs , where s ≥ 2 and B ∼
B1 , . . . , Bs for some B ∈ B. Let G′ = G(v1 ) and let G′′ = G(v2 , . . . , vs ). Note that G′ is missing the
vertex vs and similarly G′′ is missing the vertex v1 . So |G′ | < k, |G′′ | < k, and G′ , G′′ are collectible
to B. Thus, G′ , G′′ ∈ Fk−1 and so G = G′ ∨ G′′ is added to Fk in step (4).

Proposition 4.8. Suppose that we have a Bad-Event Checker using O(log mn) time and poly(m,n)
processors. Then there is an EREW PRAM algorithm to enumerate ΓR whp using poly(W ′ , ǫ−1 , n)
processors and Õ(ǫ−1 (log n)(log(W ′ n))) time.

16

BERNHARD HAEUPLER AND DAVID G. HARRIS

Proof. Proposition 4.7 shows that Fk contains all the CWDs compatible with R using at most
k nodes. Furthermore, by Corollary 2.17, whp every member of ΓR has at most O(ǫ−1 log(n/ǫ))
nodes. Hence, for K = Θ(ǫ−1 log(n/ǫ)), we have FK ⊇ ΓR whp.
The expected total number of CWD compatible with R is at most W ′ ; hence whp the total
number of such WDs is at most W ′ nO(1) . The Bad-Event Checker can be used to check whether
WDs are compatible with R, and routine parallel algorithms can be used to merge WDs. Thus, each
iteration of this algorithm can be implemented using (W ′ mn/ǫ)O(1) processors and O(log(W ′ mn/ǫ))
time. We obtain the stated bounds by using the fact that W ′ ≥ m.

4.3. Producing the final configuration. Now that we have generated the complete set ΓR , we
are ready to finish the algorithm by producing a satisfying assignment.
′
Define a graph G, whose nodes correspond to ΓR , with an edge between
W WDs G, G if they
are inconsistent. Let I be a maximal independent set of G, and let G = I. Finally define the
configuration X ∗ , which we refer to as the final configuration, by
X ∗ (i) = R(i, |G[i]| + 1)

for all i ∈ [n].
Proposition 4.9. The configuration X ∗ avoids B.
Proof. Suppose that B is true on X ∗ . Define the WD H by adding to G a new sink node v labeled
by B. Observe that G is a prefix of H. By Proposition 3.2 the WDs H, G are consistent.
We claim that H is compatible with R. By Proposition 2.9, G is compatible with R so this is
clear for all the vertices of H except for its sink node v. For this vertex, observe that for each
v (i) = R(i, |H[i]|) = R(i, |G[i]| + 1) = X ∗ (i). By Proposition 2.9, this implies
i ∈ SB we have XH
that H(v) is compatible with R as well.
So H(v) ∈ ΓR , and consequently H(v) is a node of G. Observe that H(v) and all the WDs
′
G ∈ I are prefixes of H. By Proposition 3.9, H(v) is consistent with all of them. As I was chosen
to be a maximal independent set, this implies that H(v) ∈ I.
By Proposition 3.5, this implies that H(v) is a prefix of G. This implies that |G[i]| ≥ |H(v)[i]|
for any variable i. But for i ∈ SB we have |H(v)[i]| = |H[i]| = |G[i]| + 1, a contradiction.

We thus obtain our faster parallel algorithm for the LLL:
Theorem 4.10. Suppose that the Shearer criterion is satisfied with ǫ-slack and that we have a BadEvent Checker using O(log mn) time and poly(m, n) processors. Then there is an EREW PRAM
algorithm to find a configuration avoiding B using Õ(ǫ−1 (log n) log(W ′ n)) time and (W ′ n/ǫ)O(1)
processors whp.
Proof. Use Proposition 4.8 to enumerate ΓR using Õ(ǫ−1 (log n)(log(W ′ n)) time and (W ′ n/ǫ)O(1)
processors. Whp, |ΓR | ≤ W nO(1) . Using Luby’s MIS algorithm, find a maximal independent set
of such WDs in time O(log2 (W n)) and (W n)O(1) processors. Finally, form the configuration X ∗
as indicated in Proposition 4.9 using O(log(W n/ǫ)) time and (W n/ǫ)O(1) processors. Using the
bound W ≤ n/ǫ gives the stated result.

Corollary 4.11. Suppose that the symmetric LLL criterion is satisfied with ǫ-slack, i.e., epd(1 +
ǫ) ≤ 1, and have a Bad-Event Checker using O(log mn) time and poly(m, n) processors. Then there
is an EREW PRAM algorithm to find a configuration avoiding B using Õ(ǫ−1 log(mn) log n) time
and (mn)O(1) processors whp.
P
Proof. By Proposition 4.4, we have W ′ ≤ me. Also, W = B∈B ep ≤ O(m/d). Since m ≤ nd, we
have W ≤ O(n). Now apply Theorem 4.10.


PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE LLL VIA WITNESS DAGS

17

4.4. A heuristic lower bound. In this section, we give some intuition as to why we believe
that the run-time of this algorithm, approximately O(ǫ−1 log2 n), is essentially optimal for LLL
algorithms which are based on the resampling paradigm. We are not able to give a formal proof,
because we do not have any fixed model of computation in mind. Also it is not clear whether our
new algorithm is based on resampling.
Suppose we are given a problem instance on n variables
whose distributions are all Bernoulli-q
√
n
bad
events, each of which is a threshold
for some parameter
q
∈
[0,
1].
The
space
B
consists
of
√
function on n variables, and all these events are completely disjoint from each other. By adjusting
the threshold and the parameter q, we can ensure that each bad event has probability p = 1 − ǫ.
The number of resamplings of each event is a geometric random variable, and it is not hard to see
that with high probability there will be some bad event B which requires Ω(ǫ−1 log n) resamplings
before it is false. Also, whenever we perform a resampling
of B, we must compute whether B is
√
currently true. This requires computing a sum of n binary variables, which itself requires time
Ω(log n). Thus, the overall running time of this algorithm must be Ω(ǫ−1 log2 n).
The reason we consider this a heuristic lower bound is that, technically, the parallel algorithm
we have given is not based on resampling. That is, there is no current “state” of the variables
which is updated as bad events are discovered. Rather, all possible resamplings are precomputed
in advance from the table R.
5. A deterministic parallel algorithm
In this section, we derandomize the algorithm of Section 4. The resulting deterministic algorithm
requires an additional slack compared to the Parallel Resampling Algorithm (which in turn requires
additional slack compared to the sequential algorithm). For the symmetric LLL setting, we require
that epd1+ǫ ≤ 1 for some (constant) ǫ > 0; this is the same criterion used by [3].
For deterministic algorithms, it is quite difficult to handle general classes of bad-events or asymmetric LLL criteria (whereas the randomized algorithms allow the bad-events to be almost arbitrary,
and converge under almost the same conditions as the Shearer criterion.) In [3] and [11], these issues
are discussed in more detail; our algorithm would also be compatible with most such extensions.
However in order to focus on the main case we restrict ourselves to the simplest scenario; we only
consider the symmetric criterion, and we assume that the set B contains m bad events, which are
explicitly represented as atomic events, that is, conjunctions of terms of the form Xi = j.
The paradigmatic example of this setting is the k-SAT problem. In this simplified setting, the
algorithm of [3] requires O(ǫ−1 log3 (mn)) time and (mn)O(1/ǫ) processors on the EREW PRAM. Our
main contribution in this section will be to obtain a faster algorithm, using just O(ǫ−1 log2 (mn))
time.7
The proof strategy behind our derandomization is similar to that of [3]: we first show a range
lemma (Lemma 5.4), allowing us to ignore WDs which have a large number of nodes. This will
show that if the resampling table R is drawn from a probability distribution which satisfies an
approximate independence condition, then the algorithm of Section 4 will have similar behavior
to the scenario in which R is drawn with full independence. Such probability distributions have
polynomial support size, so we can obtain an NC algorithm by searching them in parallel.
Definition 5.1. We say a probability space Ω′ is k-wise, δ-approximately independent, if for all
subsets of variables Xi1 , . . . , Xik , and all possible valuations j1 , . . . , jk , we have
PΩ′ (Xi1 = j1 ∧ · · · ∧ Xik = jk ) − PΩ (Xi1 = j1 ∧ · · · ∧ Xik = jk ) ≤ δ
7While randomized MIS algorithms appear to be faster in the CRCW model as compared to EREW, this does

not appear to be true for deterministic algorithms. The fastest known NC algorithms for MIS appear to require
O(log 2 |V |) time (in both models). Thus, for the deterministic algorithms, we do not distinguish between EREW and
CRCW PRAM models.

18

BERNHARD HAEUPLER AND DAVID G. HARRIS

Theorem 5.2 ([6]). There are k-wise, δ-approximately independent probability spaces which have
a support size poly(log n, 2k , 1/δ).
Our algorithm will be defined in terms of a key parameter K, which will determine later.
Lemma 5.3. Suppose that a resampling table R has the following properties:
(A1) For all τ ∈ ΓR we have |τ | ≤ K.
(A2) There are at most S CWDs compatible with R of size at most K.
Then, if we run the algorithm of Section 4 up to K steps, it will terminate with a configuration
avoiding B, using O(Klog(mnS) + log2 S) time and poly(K, S, m, n) processors.

Proof. By Proposition 4.7, Algorithm 3 enumerates all ΓR . By Proposition 4.9, the final configuration avoids B. The running time can be bounded noting that the total number of CWDs produced
at any step in the overall process is bounded by S.

Lemma 5.4. If there is a CWD G compatible with R with |G| ≥ K, then there exists a CWD G′
compatible with R of size K ≤ |G′ | ≤ 2K.

Proof. We prove this by induction on |G|. If |G| ≤ 2K then this holds immediately so suppose
|G| > 2K.
Suppose G has s > 1 sink nodes v1 , . . . , vs and is collectible to B. For each i = 1, . . . , s define
Hi = G(v1 , v2 , . . . , vi−1 , vi+1 , . . . , vs ).
Clearly G = H1 ∨ H2 ∨ · · · ∨ Hs . Hence there must exist i such that |G| > |Hi | ≥ |G|(1 − 1/s) ≥
|G|/2 ≥ K. Also, Hi is collectible to B and is a prefix of G, hence is compatible with R. So apply
the induction hypothesis to Hi .
Finally, suppose that G has a single sink node v labeled B. Then G − v is collectible to B and is
compatible with R. Since |G| > 2K we have |G − v| ≥ K and so we apply the induction hypothesis
to G − v.


Proposition 5.5. There are at most me(ed)t CWDs with t nodes.

Proof. Let Z denote the number of CWDs with t nodes. Then
X
X
X
(ed)−|G|
(ed)−|G| ≤ (ed)t
1 = (ed)t
Z=
CWD G
|G|=t

CWD G
|G|=t

CWD G

P
P
The term CWD G (ed)−|G| can be interpreted as CWD G w(G) under the probability vector
1
p(B) = ed
. This probability vector satisfies the symmetric LLL criterion, and so Proposition 4.4
P
gives CWD G (ed)−|G| ≤ me.

′

Proposition 5.6. For c, c′ sufficiently large constants, d ≥ 2, and K = c log(m/ǫ)
ǫ log d , the following
holds.
Suppose that B consists of atomic events on s variables and epd1+ǫ ≤ 1 for ǫ ∈ (0, 1). Suppose
′
that R is drawn from a probability distribution which is (m/ǫ)−c/ǫ -approximately, 2c sǫlog(m/ǫ)
-wise
log d
independent. Then with positive probability the following events both occur:
(B1) Every τ ∈ ΓR has |τ | ≤ 2K.
(B2) There are at most O(m) CWDs compatible with R.
Proof. By Lemma 5.4, a necessary condition for (B1) to fail is for some CWD G of size K ≤ |G| ≤
2K to be compatible with R. For any such G, let E be the event that G is compatible with R.
The event E is a conjunction of events corresponding to the vertices in G. Each such vertex event
′
depends on at most s variables, so in total E is an atomic event on at most |G|s ≤ 2Ks ≤ 2c sǫlog(m/ǫ)
log d
−c/ǫ
terms. So, by Definition 5.1, P (E) ≤ w(G) + (m/ǫ)
.

PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE LLL VIA WITNESS DAGS

Summing over all such G gives
X
P (G compatible with R) ≤

CWD G
K≤|G|≤2K

X

(w(G) + (m/ǫ)−c/ǫ ) ≤

CWD G
K≤|G|≤2K

X

w(G) +

X

19

(m/ǫ)−c/ǫ

CWD G
|G|≤2K

CWD G
|G|≥K

For any integer t, Proposition 5.5 shows there are at most me(ed)t total CWDs with t nodes,
andPhence their total weight is at most me(edp)t ≤ md−tǫ . So the first summand is at most
me t≥K d−tǫ ≤ O(md−Kǫ /ǫ); this is at most 0.1 for c′ sufficiently large.
Now let us fix c′ , and show that we can take c sufficiently
large. By Proposition 5.5, the total
P
t ≤ 2m(ed)2K . Hence the second
number of CWDs of size at most 2K is at most 2K
me(ed)
t=1
c′ log(m/ǫ)

summand is at most 2me(m/ǫ)−c/ǫ (ed) ǫ log d ; this is at most 0.1 for c sufficiently large.
Thus, altogether, we see that there is a probability of at most 0.2 that there exists a CWD (and
in particular a single-sink WD) compatible with R with more than 2K nodes.
Next suppose that all CWDs compatible with R have size at most 2K. Thus, the expected total
number of CWDs compatible with R is given by
X

CWD G
|G|≤2K

P (G compatible with R) ≤

X

CWD G
|G|≤2K

2K
X
m(ed)t )(m/ǫ)−c/ǫ
(w(G) + (m/ǫ)−c/ǫ ) ≤ W ′ + (
t=1

As we have already seen, the second summand is at most 0.1 for our choice of c, c′ . By Proposition 4.4, we have W ′ ≤ me. Thus, this sum is O(m). Finally apply Markov’s inequality.

Theorem 5.7. Suppose epd1+ǫ ≤ 1 for ǫ ∈ (0, 1) and every bad event is an atomic configuration on
at most s variables. Then there is a deterministic EREW PRAM algorithm to find a configuration

avoiding B, using O( s log(mn)/ logǫ d+log

2

(mn)

) time and (mn)O(

s+log d
)
ǫ log d

processors.

Proof. We begin with a few simple pre-processing steps. If there is any variable Xi which can take
on more than m values, then there must be one such value which appears in no bad events; simply
set Xi to that value. So we assume every variable can take at most m values, and so there are at
most mn possible assignments to the variables.
If ǫ < 1/(mn), then one can exhaustively test the full set of assignments using O(mn ) ≤ (mn)1/ǫ
processors. So we assume ǫ > 1/(mn). Similarly, if d = 1, then every bad event is independent,
and we can find a satisfying assignment exhaustively using O(ms ) processors. So we assume d ≥ 2.
′
-wise indeWe first construct a probability space Ω which is (mn)−c/ǫ -approximately, 2c sǫlog(mn)
log d
pendent on a ground set of size nK. We use this to form a resampling table R(i, x) for i ∈ [n]
s+log d

and x ≤ K. Theorem 5.2 ensures that Ω has a support size of (mn)O( ǫ log d ) . We subdivide our
processors so that ω ∈ Ω is explored by an independent group of processors; the total cost of this
log(mn)
). Henceforth, every element of this
allocation/subdivision step is O(log |Ω|) ≤ O( (s+logǫ d)
log d
probability space will be searched independently, with no further inter-communication (except at
the final stage of reporting a satisfying solution.)
′
Next, given a resampling table R, simulate the algorithm of Section 4 up to K = c log(mn)
ǫ log d .
′
By Lemma 5.6, for large enough constants c, c there is at least one element ω ∈ Ω for which all
single-sink WDs have size O(K) and for which the total number of CWDs compatible with R is
O(m). By Lemma 5.3, the algorithm of Section 4, applied to ω, produces a satisfying assignment
2
) time and using poly(m, n) processors.

using O(K log(mn) + log2 (mn)) = O( log (mn)
ǫ
Corollary 5.8. Suppose that there is a k-SAT instance with m clauses in which each variable
k/(1+ǫ)
appears in at most L ≤ 2 ek
clauses. Then a satisfying assignment can be deterministically
found on a EREW PRAM using O( log

2

(mn)
)
ǫ

time and (mn)O(1/ǫ) processors.

20

BERNHARD HAEUPLER AND DAVID G. HARRIS

Proof. Each bad event (a clause being false) is an atomic configuration on s = k variables. Here
p = 2−k and d = Lk = 2k/(1+ǫ) /e. Note that epd1+ǫ = e−ǫ < 1, and so the criterion of Theorem 5.7 is
2
satisfied. Since log d = Θ(s), the total processor count is (mn)O(1/ǫ) and the run-time is O( log (mn)
).
ǫ

Theorem 5.7 is essentially a “black-box” simulation of the randomized algorithm using an appropriate probability space. A more recent algorithm of [11] gives a “white-box” simulation, which
searches the probability space more efficiently; this significantly relaxes the constraint on the types
of bad events allowed. For problems where the bad events are simple (e.g. k-SAT), the algorithms
have essentially identical run-times.
6. Concentration for the number of resamplings
The expected number of resamplings for the Resampling Algorithm is at most W . Suppose we
wish to ensure that the number of resamplings is bounded with high probability, not merely in
expectation. One simple way to achieve this would be to run log n instances of the Resampling
Algorithm in parallel; this is a generic amplification technique which ensures that whp the total
number of resamplings performed will be O(W log n).
Can we avoid this extraneous factor of log n? In this section, we answer this question in the
affirmative by giving a concentration result for the number of resamplings. We show that whp the
number of resamplings will not exceed O(W ) (assuming that W is sufficiently large).
We note that a straightforward approach to show concentration would be the following: the
probability that there are T resamplings is at most the probability that there is a T -node WD
compatible with R; this can be upper-bounded by summing the weights of all such T -node WDs.
This proof strategy leads to the weaker result that number of resamplings is bounded by O(W/ǫ).
This multiplicative dependence on ǫ appears in prior concentration bounds. For instance, Kolipaka & Szegedy [14] shows that the Resampling Algorithm performs O(n2 /ǫ + n/ǫ log(1/ǫ)) resamplings with constant probability, and Achlioptas & Iliopoulos [1] shows that in the symmetric LLL
setting the Resampling Algorithm performs O(n/ǫ) resamplings whp. Such results have a large gap
when ǫ is small. Our main contribution is to remove this factor of ǫ−1 .
Proposition 6.1. Given any distinct bad
Q events B1 , . . . , Bs , the total weight of all WDs with s
sink nodes labeled B1 , . . . , Bs , is at most si=1 µ(Bi ).

Proof. We define a function F which which maps s-tuples (τ1 , . . . , τs ) ∈ Γ(B1 ) × · · · × Γ(Bs ) to
WDs G = F (τ1 , . . . , τs ) whose sink nodes are labeled B1 , . . . , Bs . The function is defined by first
forming the disjoint union of the graphs τ1 , . . . , τs . We then add an edge from a node B ∈ τi to
B ′ ∈ τj iff i < j and B ∼ B ′ .
Now, consider any WD G whose sink nodes v1 , . . . , vs are labeled B1 , . . . , Bs . For i = 1, . . . , j,
define τi recursively by
τi = G(vi ) − τ1 − · · · − τi−1
Each τi contains the sink node vi , so it is non-empty. Also, all the nodes in τi are connected to vi ,
so τi indeed has a single sink node. Finally, every node of G has a path to one of v1 , . . . , vj , so it
must in exactly one τi .
Thus, for each WD G with sink nodes labeled B1 , . . . , Bs , there exist τ1 , . . . , τs in Γ(B1 ), . . . , Γ(Bs )
respectively such that G = F (τ1 , . . . , τs ); furthermore the nodes of G are the union of the nodes of
τ1 , . . . , τs . In particular, w(G) = w(τ1 ) · · · w(τs ). Proposition 2.10 then gives
X

G has sink nodes
B1 ,...,Bs

w(G) ≤

X

τ1 ,...,τs

w(τ1 ) . . . w(τs ) =

s
Y
X

i=1 τ ∈Γ(Bi )

w(τ ) ≤

s
Y

µ(Bi )

i=1



PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE LLL VIA WITNESS DAGS

Theorem 6.2. Whp, the Resampling Algorithms performs O(W +

log2 n
ǫ )

21

resamplings.

Proof. Define Us to be the set of WDs which have s sink nodes and which are compatible with the
resampling table R; here s is a parameter to be specified later. Note that each of the s sink nodes
of a WD must receive a distinct label.
First, let us consider the expected size of Us . We use Proposition 6.1 to compute
X
X
E[|Us |] =
P (G compatible with R) ≤
w(G)
G has s sink nodes

≤

X

B1 ,...,Bs
distinct

G has s sink nodes

Ws
1 X
µ(B))s =
µ(B1 ) . . . µ(Bs ) ≤ (
s!
s!
B∈B

Now, suppose that the Resampling Algorithm runs for t time-steps, and consider the event E
2
that t ≥ c(W + logǫ n ) where c is some sufficiently large constant (to be determined). Let Ĝ be
the FWD of the resulting execution. Each resampling at time i ∈ {1, . . . , t} corresponds to some
vertex vi in Ĝ, and we define Hi = G(vi ).
Also, define A to be the set of indices i1 , . . . , is satisfying the properties that t ≥ i1 > i2 >
i3 > · · · > is−1 > is ≥ 1 and that ij ∈
/ Hi1 ∪ · · · ∪ Hij−1 for j = 1, . . . , s. For each tuple
a = (i1 , . . . , is ) ∈ A, define Ĝ(a) as Ĝ(vi1 , . . . , vis ). The condition ij ∈
/ Hi1 ∪ · · · ∪ Hij−1 ensures that
each vij is a sink node in Ĝ(a), and thus Ĝ(a) contains exactly s sink nodes. By Proposition 2.9 it
is compatible with R.
Further, we claim that Ĝ(a) 6= Ĝ(a′ ) for a 6= a′ . To see this, we note that we can recover
i1 , . . . , is uniquely from the graph Ĝ(a). For, suppose that B is the label of a sink node u of Ĝ(a);
in this case, if Ĝ(a)[u] contains k nodes labeled B, then vij must be the unique node in Ĝ with
extended label (B, k). This allows us to recover the unordered set {i1 , . . . , is }; the condition that
i1 > · · · > is allows us to recover a uniquely.
n
members of ΓR have size greater than
Define E ′ to be the (rare) event that more than 10 log
ǫ
10 log n
′
−Ω(1)
. By Proposition 2.17, P (E ) ≤ n
. Let X denote the set {i | |Ĝ(vi )| ≤ h} where
ǫ
n
10 log n
′
. Conditioned on the event E , we have |X| ≥ t − 10 log
; for c sufficiently large this
h =
ǫ
ǫ
implies |X| ≥ t/2.
Each Ĝ(a) is a distinct element of Us . Conditioning on the event E ′ , we therefore have:
X
X X
X
|Us | ≥ |A| ≥ |A ∩ X × · · · × X| =
···
1
i3 <i2
i1 ∈X i2 <i1
/ i1 ∪Hi2
i2 ∈H
/ i1 i3 ∈H
i3 ∈X
i2 ∈X

is <is−1
is ∈H
/ i1 ∪Hi2 ∪···∪His−1
is ∈X


By Proposition 6.5 (which we defer to after this proof), this expression is at least |X|−(s−1)h
≥
s
(t/2−sh)s
since |Hj | ≤ h for all j ∈ X.
s!
s
. Since E[|Us |] ≤
Hence, we have shown that E requires either event E ′ or that |Us | ≥ (t/2−sh)
s!
W s /s!, Markov’s inequality gives P (E) ≤ W s /(t/2 − sh)s + P (E ′ ).
t
Setting s = 4h
, we bound this as
Ws
= (4W/t)s ≤ 2−s = n−Ω(1)
(t/2 − sh)s
2

using the facts that t ≥ 8W and t ≥ Ω( logǫ n ).



Corollary 6.3. The Resampling Algorithm performs O(n/ǫ) resamplings whp.
Proof. By Corollary 2.14 we have W ≤ n/ǫ. Thus, by Theorem 6.2, the Resampling Algorithm
2

performs O( nǫ + logǫ n ) = O( nǫ ) resamplings whp.

22

BERNHARD HAEUPLER AND DAVID G. HARRIS

For the symmetric LLL, we can even obtain concentration without ǫ-slack.
Corollary 6.4. If the symmetric LLL criterion epd ≤ 1 is satisfied, then whp the number of
resamplings is O(n + d log2 n).
Proof. Set x(B) = d1 for all B ∈ B. Now a simple calculation shows that this satisfies the asymmetric
d−1 − 1 = Ω(1/d). Thus µ(B) ≤ x(B)/(1− x(B)) = 1/d, and so
LLL condition with slack ǫ = e( d−1
d )
W ≤ m/d. We also may observe that m ≤ nd. So, by Theorem 6.2, the total number of resamplings
is O(n + d log2 n) whp.

To finish this proof, we need to show the following simple combinatorial bound:
Proposition 6.5. Suppose that A is a finite set and suppose that for each integer j there is a set
Ij ⊆ A with |Ij | ≤ h. Define
X
X X
X
f (A, s, I) =
···
1
i1 ∈A

Then we have

i3 <i2
i2 <i1
i2 ∈A−Ii1 i3 ∈A−Ii1 −Ii2

is <is−1
is ∈A−Ii1 −Ii2 −···−Iis−1



|A| − (s − 1)h
f (A, s, I) ≥
s

P
Proof. Set t = |A|. We prove this by induction on s. When s = 1 then f (A, 1, I) = i1 ∈A 1 = t =
t−(1−1)h
as claimed.
1
We move to the induction step s > 1. Suppose that A = {a1 , . . . , at }, and suppose that we
select the value i1 = aj . Then the remaining sum over i2 , . . . , is is equal to f (A′j , s − 1, I), where
A′j = {a1 , . . . , aj−1 } − Ii1 . Summing over all j = 1, . . . , t gives:
f (A, s, I) =

t
X

f (A′j , s

j=1

≥
≥
=

− 1, I) ≥

t
X

j=(s−1)(h+1)
t
X

j=(s−1)(h+1)

j=s−1

j=(s−1)h+s

f (A′j , s − 1, I)



|A′j | − (s − 2)h
s−1



(j − 1 − h) − (s − 2)h
s−1

t−1−h(s−1) 

X

t
X



by inductive hypothesis


as |A′j | ≥ j − 1 − h

 

j
t − (s − 1)h
=
s−1
s

and the induction is proved.


7. Acknowledgments

Thanks to Aravind Srinivasan and Navin Goyal, for helpful discussions and comments. Thanks
to the anonymous reviewers, for many helpful comments and corrections.
References
[1] Achlioptas, D., Iliopoulos, F.: Random walks that find perfect objects and the Lovász Local Lemma. Journal of
the ACM 63-3, #22 (2016)
[2] Bissacot, R., Fernandez, R., Procacci, A., Scoppola, B.: An improvement of the Lovász Local Lemma via cluster
expansion. Combinatorics, Probability and Computing 20-5, pp. 709-719 (2011)
[3] Chandrasekaran, K., Goyal, N., Haeupler, B.: Deterministic algorithms for the Lovász local lemma. SIAM Journal
on Computing 42-6, pp. 2132-2155 (2013)

PARALLEL ALGORITHMS AND CONCENTRATION BOUNDS FOR THE LLL VIA WITNESS DAGS

23

[4] Chung, K., Pettie, S., Hsin-Hao, S.: Distributed algorithms for the Lovász local lemma and graph coloring.
Distributed Computing, pp. 1-20 (2016)
[5] Erdős, P., Lovász, L.: Problems and results on 3-chromatic hypergraphs and some related questions. In A. Hajnal,
R. Rado, and V. T. Sos, eds. Infinite and Finite Sets II, pp. 607-726 (1975)
[6] Even, G., Goldreich, O., Luby, M., Nisan, N., Velickovic, B.: Efficient approximation of product distributions.
Random Structures and Algorithms, 13(1), pp. 1-16 (1998)
[7] Fischer, M., Ghaffari, M.: Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity
hierarchy. arXiv:1705.04840 (2017)
[8] Ghaffari, M.: Towards an optimal distributed algorithm for maximal independent set. Proceedings of the 27th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 270-277 (2016)
[9] Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the Lovász Local Lemma. Journal of the
ACM, 58-6, #28 (2011)
[10] Harris, D.: Lopsidependency in the Moser-Tardos framework: beyond the Lopsided Lovász Local Lemma. ACM
Transactions on Algorithms 13-1, #17 (2016)
[11] Harris, D.: Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma.
Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1188-1203 (2017)
[12] Harris, D.: Parallel algorithms for the lopsided Lovász local lemma. arxiv:17.02547 (2017)
[13] Harvey, N., Vondrák, J.: An algorithmic proof of the Lovász local lemma via resampling oracles. Proceedings of
the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1327-1346 (2015)
[14] Kolipaka, K., Szegedy, M.: Moser and Tardos meet Lovász. Proceedings of the 43rd Annual ACM Symposium
on Theory of Computing (STOC), pp. 235-244 (2011)
[15] Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing
15-4, pp. 1036-1053 (1996)
[16] Moser, R. : Derandomizing the Lovász Local Lemma more effectively. arXiv:0807.2120 (2008)
[17] Moser, R., Tardos, G.: A constructive proof of the general Lovász Local Lemma. Journal of the ACM 57-2, #11
(2010)
[18] Shearer, J. B.: On a problem of Spencer. Combinatorica 5, pp. 241-245 (1985)

