Communication-Efficient $(1+\varepsilon)\Delta$-Edge Coloring and Lov\'asz Local Lemma

1.1 Edge coloring

• Prior work achieved 2∆−1 colors with O(n) bits, leaving open the communication cost of reducing the palette toward Vizing’s ∆+1 bound.The paper situates its coloring approach alongside distributed nibble-and-LLL algorithms [DGP98, EPS15, CHL+20] and distributed algorithms reaching ∆+1 colors.Source: §1.1 · p. 3, §1.4 · p. 8
• For fixed ε and sufficiently large ∆, a Las Vegas protocol produces a proper (1 + ε)∆-edge coloring with expected communication O(ne^-γ∆ + 1) using public randomness, or O(ne^-γ∆ + log n) using private randomness.The communication is O(1) when ∆ is sufficiently large relative to log n.Source: §1.1 · p. 4

1.2 Constructive Lov´asz local lemma

• The two-party constructive LLL finds an assignment avoiding all bad events under constant slack, with communication governed by the number of shared variables rather than their domain sizes.When Mph = O(N), expected communication is O(N), even if shared variables have arbitrarily large domains.Source: §1.2 · p. 5
• The two-party LLL is also applied to several classical problems with natural LLL formulations, yielding communication-efficient protocols.The introduction places this work among broader two-party graph-problem and constructive or distributed LLL research.Source: §1.2 · p. 5, §1.4 · pp. 8–9

1.3 Technical overview

• The LLL protocol batches resampling before communication and synchronizes shared-variable counters, avoiding transmission of large-domain values.Expected resamplings decrease geometrically across rounds under the LLL condition with slack.Source: §1.3 · p. 6
• The coloring construction uses a shared random palette ordering at each vertex to give Alice and Bob disjoint permitted palettes, while edge assignments remain private.Palette overloads and fallback-graph growth are the local failures handled by the LLL.Source: §1.3 · p. 7

2 Constructive Lov´asz local lemma

• The section’s efficiency analysis combines geometric decay in expected resamplings across rounds with encoding only net changes to shared counters.This is the stated route from the protocol to the communication bound in Theorem 2.Source: §2 · p. 9

2.1 Moser–Tardos resampling and public tables

• Public resampling tables let both parties reconstruct shared-variable values from synchronized counters without transmitting those values.Independent table entries consumed in order preserve the distribution of ordinary Moser–Tardos resampling.Source: §2.1 · p. 9

2.2 The communication protocol

• The parties alternate exhaustive rounds, communicating net shared-counter updates; a round with no updates from round 2 onward guarantees that no bad event remains.Each party resamples its occurring bad events until none remain, and the resulting execution is a valid Moser–Tardos execution.Source: §2.2 · p. 10

2.3 Witness trees

• The analysis represents resamplings with proper witness trees; distinct resampling times yield distinct trees, enabling witness-tree bounds to control resampling counts.The tree is built by scanning earlier resamplings backward and attaching dependent events below deepest eligible nodes.Source: §2.3 · p. 11

2.4 Witness-tree tail and round complexity

• The late-round depth result states that every resampling performed in any round j ≥ 3 has a witness-tree depth of at least j − 2, imposing a round-dependent minimum depth.Source: §2.4 · p. 13

2.5 Encoding the net update vectors

• The update encoding communicates the increment total and a rank identifying the nonnegative update vector, adapting to the number of counter increments.A control bit indicates whether the total is zero; no further data are sent when it is.Source: §2.5 · p. 14

2.6 Communication complexity

• Summing expected per-round update-message costs using geometric decay gives the communication analysis across all rounds.The section first bounds each message in terms of expected shared-counter increments, then sums those bounds and accounts for one control bit per invoked round.Source: §2.6 · p. 15
• The expected number of rounds is O(1 + Mph).The proof derives this bound from the expected number of resamplings and the protocol’s round analysis.Source: §2.6 · p. 16
• The theorem bounds expected communication by an expression involving Mph and a logarithmic factor.The supplied passage omits the logarithm’s argument.Source: §2.6 · p. 16
• The protocol almost surely terminates and never outputs an invalid assignment.Its expected total number of resamplings is finite.Source: §2.6 · p. 16

3 Edge coloring

• Disjoint permission sets let Alice and Bob safely reuse regular palettes, while separate fallback palettes prevent conflicts between their fallback edges.Each party routes edges to a regular palette permitted at both endpoints; edges with no such palette go to its fallback graph.Source: §3 · p. 17

3.2 Parameters

• For sufficiently large Δ depending on ε, the palettes fit within (1 + ε)Δ colors, and prefix and suffix permission sets remain disjoint.At each vertex, Alice’s and Bob’s permission sets are a prefix and suffix of a shared permutation, with total size at most q.Source: §3.2 · p. 19

3.3 Probability analysis

• For each vertex and party, regular-palette overload probability is at most e^-c1Δ and fallback overload probability is at most e^-c2Δ.The constants c1 and c2 are positive and depend only on ε.Source: §3.3 · pp. 21–22

3.1 The construction

• The construction uses shared vertex permutations to assign permissions and private edge permutations to route edges, after which each party colors its subgraphs locally.Regular subgraphs use their corresponding palettes, while the two fallback graphs use separate palettes; Vizing’s theorem supplies the local colorings.Source: §3.1 · p. 18, §3.4 · p. 22

3.4 The LLL instance

• For sufficiently large Δ depending only on ε, the LLL instance has N = n, M = 2n, p = e^-cΔ, h = Δ + 1, and D = 2Δ^2 + 1.Its bad events are degree-threshold violations in a party’s regular subgraphs or fallback graph.Source: §3.4 · p. 22
• The bad-event dependency degree is at most D = 2Δ^2 + 1, since dependent events must be centered within distance two.There are at most 2Δ^2 + 1 other dependent events centered among vertices within distance two.Source: §3.4 · p. 23

3.5 Applying the two-party LLL protocol

• With N = n, M = 2n, p = e^-cΔ, D = 2Δ^2 + 1, and h = Δ + 1, λ = e·p(D + 1) = e^-Ω(Δ) ≤ 1/2 for sufficiently large Δ.Thus Theorem 2 applies with constant slack.Source: §3.5 · p. 23
• When Δ is at least a sufficiently large constant depending only on ε, the resampling stage terminates almost surely; the cited analysis also considers expected communication and round costs.Source: §3.5 · pp. 23–24

3.6 Completing the proof

• Newman’s theorem converts the public-coin protocol to a private-coin Las Vegas protocol with O(log n) additional expected bits [KN97, Exercise 3.15].The conversion uses log log K = O(log n) for the number of possible input pairs.Source: §3.6 · pp. 24–25
• For every fixed ε in (0, 1), when Δ is sufficiently large, a Las Vegas two-party protocol produces a proper (1 + ε)Δ-edge coloring with expected communication O(ne−γΔ + 1) publicly and O(ne−γΔ + log n) privately.Here γ > 0 depends only on ε.Source: §3.6 · p. 24
• After resampling, local colorings combine into a valid coloring using at most (1 + ε)Δ colors, with no further communication, so the protocol is Las Vegas.The proof verifies that colors from different palettes are disjoint and edges sharing a palette cannot conflict at an endpoint.Source: §3.6 · p. 25

4 Further applications

• The applications use public variables and domains with disjoint private constraint sets; small bad-event probabilities can offset many constraints and shared variables in the communication bound.The section applies Theorem 2 to standard LLL formulations and then uses Lemma 18 for private-coin protocols.Source: §4 · p. 25

4.1 Satisfiability

• In k-SAT, a clause’s violation probability 2^-k compensates for potentially many clauses, whose number can exceed N.A uniformly random assignment violates any fixed clause with probability 2^-k; this factor offsets the large occurrence bound in the communication calculation.Source: §4.1 · p. 26
• For bounded-occurrence k-SAT, Alice and Bob can find a satisfying assignment with O(N) expected bits and O(log N) expected rounds using private coins.The symmetric-LLL argument matches the asymptotic dependence on k of the cited threshold result but not its optimal constant.Source: §4.1 · pp. 26–27

4.2 Hypergraph 2-coloring

• In hypergraph 2-coloring, a fixed hyperedge is monochromatic with probability 2^(1-k), compensating for potentially many hyperedges in the communication bound.The section also gives an o(N) bound from Theorem 2 when D + 1 = o(2^k), while noting that private-coin conversion overhead may dominate that bound.Source: §4.2 · pp. 27–28
• For partitioned k-uniform hypergraph 2-coloring, the parties obtain a private-coin Las Vegas protocol using O(|V|) expected bits and O(log |V|) expected rounds.The stated guarantee applies when D + 1 ≤ 2^(k-3).Source: §4.2 · pp. 27–28

4.3 List coloring with bounded color degree

• With public lists of size at least Q and color degree at most d, where Q ≥ 8d, proper list coloring takes O(n) expected bits and O(log n) expected rounds using private coins.Here, color degree counts neighbors that could conflict at a vertex if it receives a given color.Source: §4.3 · p. 28
• When Q/d = ω(1), the list-coloring communication cost is sublinear in n; equal lists of size 8∆ also give an O(n)-communication alternative for O(∆)-vertex coloring.The cited earlier work obtains the same O(n) communication bound using ∆ + 1 colors.Source: §4.3 · p. 30

• With public randomness, expected communication is sublinear for Δ=ω(1) and constant for Δ≥Cε log n; private coins add O(log n) expected bits.Source: §5 · p. 30
• The two-party constructive LLL applies under the symmetric LLL condition with constant slack and is illustrated on other classical problems.Source: §5 · p. 30

Approaching Vizing’s bound

• The authors ask whether Δ+O(1) or Δ+1 edge coloring can use O(n) expected communication, and whether sublinear communication is possible as Δ grows.They also ask whether the sufficiently-large-Δ assumption can be removed.Source: §5 · p. 30

Communication as a function of the degree

• Whether the ne^-Ω(Δ) communication dependence is optimal remains open; it is also unknown whether communication decreases with Δ for Δ+1 vertex coloring.Source: §5 · p. 30

Deterministic protocols

• A deterministic version of the sublinear-communication result remains open, and the authors say their approach uses randomness essentially.A deterministic analogue may require substantially different ideas.Source: §5 · p. 30

• The authors report extensive use of ChatGPT and Claude in developing and writing the paper, while stating that the human authors verified the results and take responsibility for the contents.Source: AI disclosure · pp. 30–31