A Constructive Proof of the General Lovász Local Lemma
Journal of the ACM, 2010 · paper · Computer science
Gives an algorithmic proof of the general Lovász Local Lemma, which previously only showed that certain combinatorial objects exist. The authors reformulate and improve earlier constructive results so they apply to almost all known uses of the lemma.
Checked: PDF from arxiv.org, fetched 4 Oct 2026. Page numbers are those of that PDF.
2 findings
Substance Theorem 1.3 states the parallel algorithm takes "an expected O(1/ε log ∑_{A∈𝒜} x(A)/(1−x(A))) steps". When S=∑x(A)/(1−x(A)) is close to or below 1, this bound tends to zero or goes negative, yet the expected number of steps stays bounded away from zero.
- p. 4 Theorem 1.3, expected number of parallel steps
O(1/ε log ∑_{A∈𝒜} x(A)/(1 − x(A)))
- p. 7 Section 4, concluding sentence
This bound easily implies Theorem 1.3.
Only the authors can say what is right here.
Judge's note: I checked the theorem statement on p.4 and the proof on p.7. The proof ends with Q(k) ≤ (1−ε)^k S and "This bound easily implies Theorem 1.3." I reworked the counterexample against the stated hypotheses, which are only x: 𝒜→(0,1) and ε>0. Take m independent events A_i with Pr=1/(2m), x(A_i)=1/m and ε=1/2. Γ(A_i) is empty, so the hypothesis Pr[A] ≤ (1−ε)x(A) holds with equality. Then S=m/(m−1), and (1/ε)·log S ≈ 2/(m−1), which tends to 0. However, the parallel algorithm takes at least one step whenever some event holds at the start, and that happens with probability 1−(1−1/(2m))^m, which tends to 1−e^{−1/2}≈0.39. No fixed constant in the O(·) can cover both, so the formula is false as printed for S near 1, and for S<1 the logarithm is negative. Summing the proved tail bound, E ≤ ∑_k min(1,(1−ε)^k S), gives O((1/ε)(1+log S)), or equivalently log(1+S). So the gap is a missing additive term, not a fault in the proof technique. The paper states no convention that would cover it. Only the authors can say which form they intended.
Second check: another model agreed
Report a problem with this finding
Wording Section 4, second display: "(1−ε)^k ∑_{A∈𝒜} ∑_{τ∈𝒯_A} ∏_{v∈V(τ)} x′([v]) = (1−ε)^k ∑_{A∈𝒜} x(A)/(1−x(A)) ∑_{τ∈𝒯_A(k)} p_τ". The sum on the left of the '=' runs over 𝒯_A, but the sum on the right runs over the subset 𝒯_A(k).
- p. 7 Section 4, second Q(k) display
x(A)/(1 − x(A)) ∑_{τ∈T_A(k)} p_τ
- p. 7 Section 4, final displayed chain, equality
∑_{τ∈𝒯_A} ∏_{v∈V(τ)} x′([v])
- p. 7 Section 4, right-hand side of the same equality
∑_{τ∈𝒯_A(k)} p_τ
- p. 7 Section 4, displayed bounds on Q(k)
= (1 −ε)k X A∈A x(A) 1 −x(A) X τ∈TA(k) pτ
Only the authors can say what is right here.
Judge's note: The p.7 page image shows the subscripts as quoted, so this is not an extraction artefact. The first display widens the sum from 𝒯_A(k) to 𝒯_A in its last step. Lemma 3.1 gives ∏x′ = x(A)/(1−x(A))·p_τ for each tree. Summing that over 𝒯_A gives x(A)/(1−x(A))·∑_{𝒯_A} p_τ, and this is at least the printed sum over 𝒯_A(k). The single-vertex tree has p_τ>0 and lies outside 𝒯_A(k) when k≥2, so it is strictly larger. The printed '=' is therefore false. The fix is to write 𝒯_A on the right, or 𝒯_A(k) throughout. Either way the final bound Q(k) ≤ (1−ε)^k ∑ x(A)/(1−x(A)) still holds, because the sum of p_τ is at most 1. The step is faulty but the stated result stands, so severity is S3.
Second check: another model agreed
Report a problem with this finding
10 minor (typos and the like; most checked by the judge only)
Reference or label Conclusion, p.11: "Luby's randomized algorithm finds a maximal independent set in any graph in logarithmic expected time" cites no reference, and the reference list on p.12 has no Luby entry.
- p. 11 Section 7, paragraph 2
Luby’s randomized algorithm finds a maximal independent set in any graph in logarithmic expected time
Only the authors can say what is right here.
Judge's note: I checked the reference list on the p.12 image and searched the text: Luby appears only in the conclusion and is never cited. Every other prior result is cited by key, so a reference is missing.
Second check: another model agreed
Report a problem with this finding
Reference or label References [Knu69], [KST93] and [Wel08] appear in the reference list but are never cited in the text.
- p. 12 References
[Knu69]
- p. 12 References
[KST93]
- p. 12 References
[Wel08]
Judge's note: A text search for each key, and for Knuth, Kratochvíl and Welzl, finds them only in the reference list. Welzl appears only in the Acknowledgements, not as a citation. All other entries, including BKS03 and Mos06, are cited.
Second check: another model agreed
Report a problem with this finding
Wording Intro p.2: "in [Mos08] ... up to a neighborhood size of roughly 2^{k/2} and finally in [Mos09], the threshold was lowered to roughly 2^k/32": the threshold went up from 2^{k/2} to 2^k/32, so 'lowered' describes the opposite direction (only the gap shrank).
- p. 2 Introduction, history paragraph
the threshold was lowered to roughly 2
- p. 2 Introduction, paragraph on prior work
neighborhood size of roughly 2k/2 and finally in [Mos09], the threshold was lowered to roughly 2k/32
- p. 2 Introduction, paragraph 2
the threshold was lowered to roughly 2k/32
Judge's note: Page 2 image: the expression is 2^k/32 (the superscript is k alone, then /32), not 2^{k/32}. So the sequence 2^{k/48}, 2^{k/8}, 2^{k/4}, 2^{k/2}, 2^k/32 does increase steadily toward 2^k/e, and the reviewer notes that read '2^{k/32}' or suggest k/5 or k/16 misread the page. The only remaining point is the word 'lowered', which applies to the threshold even though the threshold rose. It could be read loosely as referring to the gap, so this is a minor wording point.
Second check: another model agreed
Report a problem with this finding
Wording Section 5, p.8: k is used both for tree size ("at least k vertices is bounded by (1−ε)^k ... O(m(1−ε)^k)") and for the degree bound of Theorem 1.4 ("|Γ_A(A)| ≤ k"; Lemma 5.1 "bounded by k", range [u,(k+1)u]).
- p. 8 Section 5, third paragraph
least k vertices is bounded by (1 − ε)^k
- p. 8 Lemma 5.1
bounded by k as required in the theorem
- p. 4 Theorem 1.4
|ΓA(A)| ≤k for some constant k
- p. 8 Section 5, paragraph 3
least k vertices is bounded by
Judge's note: Pages 4 and 8 confirm the two meanings on the same page of the derandomization argument. The meaning can be recovered from context, so this is a notation ambiguity only.
Second check: another model agreed
Report a problem with this finding
Typo Section 5, p.8: "x̃(A) := (1 − ϵ/2)x(A) for all A and ϵ by ϵ/2" uses the glyph ϵ, while Theorems 1.3/1.4 and the next paragraph use ε for the same parameter.
- p. 8 Section 5, second paragraph
x̃(A) := (1 − ϵ/2)x(A) for all A and ϵ by ϵ/2
- p. 8 Section 5, third paragraph
O(m(1 − ε)^k)
- p. 8 Section 5, paragraph 2
˜x(A) := (1 −ǫ/2)x(A) for all A and ǫ by ǫ/2
- p. 4 Theorem 1.4
Pr[A] ≤(1 −ε)x(A)
Judge's note: The page 8 image shows visibly different epsilon glyphs in paragraphs 2 and 3. This is cosmetic.
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Lemma 3.1: "accounts for the fact the the root is always born" should read "the fact that the root".
- p. 6 Proof of Lemma 3.1
accounts for the fact the the root is always born
- p. 6 Proof of Lemma 3.1
the fact the the root is always born
- p. 6
factor accounts for the fact the the root is always born
Judge's note: The page 6 image shows 'the fact the the root'.
Second check: code check
Report a problem with this finding
Typo Lemma 3.1: "Let τ a fixed proper witness tree" is missing the word 'be'.
- p. 6 Lemma 3.1
Let τ a fixed proper witness tree
Judge's note: The page 6 image shows the statement of Lemma 3.1 without 'be'.
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Lemma 3.1: the factors "(1 − x([u]))" for u ∈ W_v, u ∈ Γ+([v]) and u ∈ Γ([v]) apply the bracket [·] to events u, but [v] := σ_T(v) is defined only for tree vertices.
- p. 6 Proof of Lemma 3.1, displayed formulas
∏_{u∈W_v} (1 − x([u]))
- p. 6 Proof of Lemma 3.1, all three displays
(1 −x([u]))
Judge's note: The definition [v] := σ_T(v) for v ∈ V(τ) is in the text on p.5. In all three displays on p.6, u ranges over sets of events, so x(u) is meant. This matches x'(B) = x(B)∏_{C∈Γ(B)}(1−x(C)). It is a harmless abuse of notation and the derivation is unaffected.
Second check: none (judge only)
Report a problem with this finding
Typo Conclusion, p.11: "maximal independent set of violated vertices of the dependence graph" and "finding the violated indices" differ from the defined terms 'dependency graph' and 'violated events'.
- p. 11 Section 7, second paragraph
vertices of the dependence graph
- p. 11 Section 7, paragraph 2
violated vertices of the dependence graph
- p. 11 Section 7, paragraph 2
Sampling and finding the violated indices is typically faster
- p. 11 Section 7
maximal independent set of violated vertices of the dependence graph
Judge's note: Text search finds 'dependence graph' only on p.11; 'dependency graph' is used everywhere else, including in the same section. The page 11 image confirms both phrases. This is cosmetic.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [Bec91]: "Jószef Beck" — the first name is misspelled.
- p. 12 Reference [Bec91]
Jószef Beck
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: Beck's first name is spelled 'József'. The p.12 image shows 'Jószef' as printed.
Second check: none (judge only)