PaperlayerView exact revision on arXiv

Source-linked AI summary

New Constructive Aspects of the Lovasz Local Lemma

Bernhard Haeupler, Barna Saha, Aravind Srinivasan

arXiv:1001.1231v5cs.DScs.DM

TL;DR

The paper addresses how to construct LLL-guaranteed structures when there are superpolynomially many bad events, event detection is hard, or some bad events may remain. It exploits the randomness of the Moser–Tardos output distribution to obtain polynomial-in-variable algorithms and demonstrates them on allocation, coloring, Ramsey, and MAX-k-SAT problems. The results include a first constant-factor Santa Claus approximation and the first algorithmic LLL applications allowing a limited number of bad events.

  • Problem

    Existing LLL algorithms can face superpolynomially many bad events, computationally hard event detection, or settings where only most bad events must be avoided.

  • Method

    The paper analyzes the Moser–Tardos output distribution and uses its approximation to the LLL distribution, together with core-event selection and union bounds, to construct solutions efficiently.

  • Results

    The approach gives polynomial-in-n algorithms, a first constant-factor approximation for Santa Claus, efficient coloring and Ramsey constructions, and MAX-k-SAT algorithms that allow some violated clauses.

  • Takeaways & Limitations

    The work extends constructive LLL methods from avoiding every bad event to exploiting residual randomness when some events may remain.

  • Takeaways & Limitations

    The algorithms allow running time polynomial in log(1/δ), and the paper notes that deterministic methods remain difficult when the event count is superpolynomial.

Abstract

from arXiv · show

The Lovász Local Lemma (LLL) states that the probability that none of a set of "bad" events happens is nonzero if the probability of each event is small compared to the number of bad events it depends on. A series of results have provided algorithms to efficiently construct structures whose existence is (non-constructively) guaranteed by the full asymmetric LLL, culminating in the recent breakthrough of Moser & Tardos. We show that the output distribution of the Moser-Tardos procedure has sufficient randomness, leading to two classes of algorithmic applications. We first show that when an LLL application provides a small amount of slack, the running time of the Moser-Tardos algorithm is polynomial in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events (or where finding a bad event that holds is computationally hard). We demonstrate our method on applications including: the first constant-factor approximation algorithm for the Santa Claus problem, as well as efficient algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. Second, we show applications to cases where a few of the bad events can hold, leading to the first such algorithmic applications of the LLL: MAX $k$-SAT is an illustrative example of this.

1 Introduction

The paper develops new constructive uses of the Lovász Local Lemma by exploiting randomness in the Moser–Tardos output distribution. It gives polynomial-in-variables algorithms despite superpolynomially many or hard-to-detect bad events, and extends LLL algorithms to settings where some bad events may remain.

  • Algorithmic framework: With small slack, Moser–Tardos requires at most O(n^2 log n) resampling steps in known applications, and often O(n · polylog(n)).This enables constructive algorithms whose running time depends on the number of variables rather than the number of bad events.
  • Core contribution: The Moser–Tardos output distribution approximates the LLL distribution closely enough to support constructive probabilistic analyses.For every event B, the same upper bound f_A(B) · Pr[B] applies in the output distribution.
  • Algorithmic framework: The paper gives polynomial-in-n algorithms even when the LLL uses superpolynomially many events or detecting a true event is computationally hard.A small polynomial-sized core of events can be selected and avoided, while a union bound handles non-core events.
  • Applications that avoid all bad events: The approach yields a first constant-factor approximation algorithm for the Santa Claus problem and efficient constructions for several coloring and Ramsey-type problems.Applications include acyclic edge coloring, non-repetitive graph coloring, and general Ramsey-type graph construction.
  • Applications that avoid many bad events: The paper extends LLL applications beyond the all-or-nothing regime by efficiently constructing assignments in which some bad events remain.For MAX-k-SAT, if each clause overlaps with about α2^k/e clauses for 1 < α < e, the algorithm violates at most (e ln(α)/α + o(1)) · m · 2^-k clauses for large k.
  • Scope and assumptions: The algorithms assume a representation in which log(1/δ) is polynomially bounded, as holds in the applications discussed.The paper states that typically δ ≥ exp(−O(n log n)), giving log(1/δ) = O(n log n).

2 LLL-Distribution

The paper defines the conditional LLL-distribution and shows that the Moser–Tardos output approximately preserves its event-probability bounds. This approximate sampling view makes probabilistic LLL arguments constructive.

  • Conditional LLL-distribution: Rejection sampling produces the conditional LLL-distribution by repeatedly sampling variables until no bad event holds, but it can require exponentially many resamplings.The Moser–Tardos algorithm is more efficient but does not automatically produce the same conditional distribution.
  • Conditional LLL-distribution: Under the LLL conditions, the conditional LLL-distribution is well-defined and bounds the probability of any event B determined by the variables.The paper notes that this bound is especially useful when B depends on relatively few bad events.
  • Moser–Tardos output: The Moser–Tardos output distribution approximates the conditional LLL-distribution by satisfying the same upper bound for events that may occur during execution or remain true in the output.For event B, the bound is Pr[B] · (∏_{C∈Γ(B)}(1−x(C)))^-1.
  • Constructive consequences: This approximate sampling theorem turns proofs based on the conditional LLL-distribution into constructive algorithms.The paper states that all of its constructive results are based on this theorem.

3 LLL Applications with Super-Polynomially Many Bad Events

The paper bounds Moser–Tardos resampling in terms of the number of underlying variables and extends it to super-polynomial event families through efficiently verifiable cores. With slack, these techniques yield efficient Monte Carlo and sometimes parallel algorithms despite difficult event detection.

  • Resampling bounds: Theorem 3.1 bounds expected resamplings by O(n/ε) when ε>0, with termination within λO(n/ε) resamplings with probability 1−exp(−λ).For ε=0, the expected bound is T max_A 1/(1−x(A)), with a corresponding 1−1/λ tail bound.
  • Resampling bounds: Theorem 3.1 exploits dense variable-sharing graphs to make resampling depend on n rather than the potentially much larger number m of bad events.Events sharing a variable form cliques, yielding at least m^2/(2n)−m/2 dependency edges when m≫n.
  • Scope and limitations: The running-time estimate T=O(n log(1/δ)) is tight in some cases, although the paper reports O(n log n) running time in most known applications even when ε=0.The bound can be achieved using isolated constant-probability events for each variable.
  • Efficient verifiability: When m is super-polynomial, direct Moser–Tardos use may be inefficient because finding violated events can be computationally hard.Efficient verifiability requires finding a currently holding event or certifying that none holds.
  • Efficient verifiability: An efficiently verifiable core A′ lets a modified Moser–Tardos algorithm resample only core events while controlling non-core failure probabilities.Theorem 3.3 gives the core-based construction, while Theorem 3.4 obtains a polynomially sized core under constant exponential ε-slack.
  • Monte Carlo applications: Theorem 3.4 gives a Monte Carlo algorithm using O(n/ε^2) resamplings and succeeding with probability at least 1−n^−c for any desired constant c>0.The result uses an efficiently verifiable core and bounds the remaining failure probability by n^−c.
  • Monte Carlo applications: The core can often be processed in parallel, yielding RNC algorithms after parallel event evaluation and maximal-independent-set computation.The paper notes that logarithmically many resampling rounds suffice in this setting.
  • Scope and limitations: Efficient deterministic algorithms remain difficult when m is super-polynomial because existing derandomization methods explicitly depend on all events or use domains of size poly(m).This contrasts with the Monte Carlo approach, which avoids representing all bad events explicitly.

4 A Constant-Factor Approximation Algorithm for the Santa Claus Problem

The paper makes the non-constructive LLL-based Santa Claus approximation constructive, yielding the first randomized constant-factor approximation algorithm in expected polynomial time.

  • The Santa Claus problem is a restricted max-min allocation problem in which each item has an intrinsic value and each child values it at that value or zero.
  • Motivation: Prior constant integrality-gap proofs for the configuration LP were non-constructive, leaving a constant-factor approximation algorithm open.
  • Algorithm: The authors constructivize Feige’s LLL-based proof by efficiently solving the associated set-system problem, with a constant-factor loss in approximation.
  • Analysis: The reduction process keeps the system parameters controlled: l and β become constant, while the running time to avoid all bad events is O(m).
  • Algorithm: Theorem 3.4 makes the LLL construction feasible despite exponentially many bad events by producing a valid reduce-k system with high probability.
  • Result: There exists a constant α > 0 and a randomized expected-polynomial-time algorithm assigning every child items of total valuation at least α · OPT.

5 Non-repetitive Coloring of Graphs

The paper turns the LLL proof of non-repetitive graph coloring into an efficient Monte Carlo construction, overcoming exponentially many bad events and hard event detection at a small color-cost.

  • Problem: A non-repetitive edge coloring forbids any simple path from having identical color sequences in its two halves; the minimum required colors is the Thue number π(H).
  • Problem: The prior LLL proof used exponentially many bad events, while checking whether a coloring is non-repetitive is coNP-Hard even with four colors.
  • Method: The authors apply their constructive LLL theorem with slightly more colors, creating sufficient slack for efficient verification of relevant short paths.
  • Baseline: The LLL establishes existence of a non-repetitive coloring with O(∆^2) colors before constructivization.
  • Result: For every constant ǫ > 0, a Monte Carlo algorithm produces a non-repetitive coloring using at most c∆^(2+ǫ) colors.

6 Ramsey-type Bounds

The method directly constructivizes LLL-based existence proofs for Ramsey-type graphs, including off-diagonal bounds and graphs avoiding specified subgraphs across large vertex sets.

  • Problem: Ramsey numbers capture the threshold at which every red-blue coloring contains either a red K_s or a blue K_t.
  • Problem: The paper targets the fixed-s off-diagonal setting, where constructing graphs matching the best known bounds is a longstanding problem.
  • Method: The authors make the LLL-based proof constructive to achieve the best known bound for off-diagonal Ramsey numbers with fixed s.
  • Result: The method provides Monte Carlo constructions on n vertices with no specified subgraph U in any s-vertex set and no specified subgraph W in any t-vertex set.
  • Method: With exponential slack, Theorem 3.4 typically applies directly, while fixed-s cases can alternatively verify only selected events through Theorem 3.3.

7 Acyclic Edge Coloring

The paper converts asymmetric LLL proofs for acyclic edge coloring into randomized expected-polynomial-time algorithms, matching known bounds and extending them under large-girth assumptions.

  • Problem: Acyclic edge coloring is a proper edge coloring in which every cycle receives more than two colors.
  • Motivation: Earlier asymmetric-LLL bounds were non-constructive, including the 16∆ bound for general graphs.
  • Method: The constructive theorem efficiently detects violated events and converts the 16∆ LLL proof into an algorithm.
  • Result: There is a randomized expected-polynomial-time algorithm using 16∆ colors for graphs with n edges and maximum degree ∆.
  • Large-girth case: For graphs of girth Ω(∆log ∆), the method yields a randomized expected-polynomial-time acyclic coloring using ∆ + 2 colors.

8 Beyond the LLL Threshold

The paper extends constructive LLL techniques beyond the threshold by selecting a sparse core of bad events, satisfying it constructively, and controlling violations outside the core. For MAX-k-SAT, this yields polynomial-time assignments that satisfy the core clauses while limiting the remaining violations.

  • MAX-k-SAT: MAX-k-SAT seeks an assignment violating as few clauses as possible when satisfying every clause may be unavailable under denser dependencies.A random assignment violates at most m2^-k clauses in expectation, while the LLL can guarantee zero violations only below its dependency threshold.
  • Core construction: A sparse core of clauses can satisfy the LLL conditions even when the full formula lies beyond the LLL threshold.The core is selected so its internal dependencies are bounded, enabling the Moser-Tardos algorithm to satisfy all core clauses.
  • MAX-k-SAT: A randomized polynomial-time algorithm satisfies every core clause and violates at most an (1 + θ)2^-ke^γ fraction of the remaining clauses.The guarantee holds with high probability for any θ ≥ 1/poly(n, m), under the stated core-dependency conditions.
  • Constructive extension: The core-selection and conditional-distribution analysis converts the nonconstructive argument into a polynomial-time randomized algorithm for efficiently verifiable events.Theorem 8.4 bounds the expected number of violated events by (1 + o(1))λ(α) · mp.
  • Core construction: An LLL-based core construction can produce a larger core than uniform random selection and slightly sharpen the resulting bounds.The alternative construction applies the LLL to bad events describing excessive core neighborhoods.
Loading 1001.1231v5…