{"id":"cdcbd910-e71d-43e2-a444-dd560a29aca0","arxiv_id":"1908.06270","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For the distributed LLL with each variable affecting at most three events, the paper gives an O(d^2 + log* n) deterministic algorithm under the criterion p < 2^{-d}, and shows the threshold p = 2^{-d} is sharp.","lead":"This paper proves that a distributed version of the Lovász Local Lemma can be solved in O(log* n) rounds deterministically when the bad events are unlikely enough (p < 2^{-d}), for variables that affect at most three events. It pins down a sharp phase transition at p = 2^{-d}, separating this fast regime from problems known to require much more time.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.5's Appendix A proof uses an incorrect root formula: with a=1,b=2 the printed x1 is outside the feasible interval and c(x1) != f, so the Srep characterization is not established as written.","rationale":"Good-faith reading: the paper's central contribution is a deterministic O(d^2 + log* n) algorithm for LLL at p < 2^-d for rank at most 3, and the proof hinges on maintaining a representable-triple invariant. The high-level strategy is coherent: a linearity argument forces either a non-evil value or a chord violating incurvedness, and the convexity of f is used to rule that out. I checked Lemma 3.6's Hessian computation numerically and symbolically; it is plausible and the determinant positivity argument is sound on the stated domain. The rank-2 warm-up is also clean. The point where the written proof actually breaks is Lemma 3.5's derivation of the boundary function f. The quadratic root formula in Appendix A has an evident algebra error: converting the stationary equation to x^2 - px + p = 0, the roots are (p ± sqrt(p^2 - 4p))/2, not /4. The printed formula is inconsistent with the right-hand side of the same displayed line and, under the literal definition, fails for a < b. Because Lemma 3.5 feeds directly into Lemma 3.7, and Lemma 3.7 is the only defense against evil values in Lemma 3.9, this is load-bearing. This is not an objection to the truth of the theorem: the error appears fixable and the rank-2 reduction issue is secondary. But the manuscript as it stands does not give a complete proof of the Srep characterization, so the conditional acceptance is appropriate. I partially agree with the reader: the Hessian was not the real soft spot; the root computation is.","tokens_in":18711,"tokens_out":47991,"duration_ms":482875,"concrete_test":"Recompute Lemma 3.5 for the case (a,b)=(1,2). First, substitute the paper's literal x1 = p/2 - sqrt(p^2 - 4p)/4 into c(x) and compare with f(1,2). Then solve the quadratic exactly and check that the unique root in [1/2,1] is x = (2 - sqrt(12))/(-2) ≈ 0.732, that it gives c = 2 - sqrt(3), and that the resulting triple (a,b,c) is representable with edge values a1=x, a2=a/x, b1=2-x, b3=b/(2-x), c2=2-a/x, c3=2-b/(2-x). If the corrected root restores the equality Srep = {(a,b,c) in R^3_{>=0} : a+b<=4, c<=f(a,b)}, the proof is salvageable; if not, the incurvedness argument and Theorem 1.3 no longer have a foundation.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 3.5 is the exact characterization of Srep used in Lemma 3.7 to prove incurvedness, which is the only mechanism in Lemma 3.9 that rules out evil values and makes the Variable Fixing Lemma true. In the Appendix A proof of Lemma 3.5, the stationary points of c(x) = (2 - a/x)(2 - b/(2 - x)) are printed as x_{1,2} = p/2 ± sqrt(p^2 - 4p)/4, p = a(4 - b)/(a - b). This is algebraically wrong: the denominator should be 2, not 4, and the left- and right-hand sides of the displayed equation do not agree. For a concrete instance a=1,b=2 (valid, a+b=3), p=-2, the printed x1 = -1 - sqrt(12)/4 ≈ -1.866 lies outside the feasible interval [a/2, 2-b/2] = [0.5,1], and c(x1) ≈ 3.76, whereas f(1,2) = 2 - sqrt(3) ≈ 0.268. The actual maximizer is (2 - sqrt(12))/(-2) ≈ 0.732. Since the proof of Lemma 3.5 as written does not identify the maximizing x, the set Srep is not rigorously characterized, and Lemma 3.7 and Lemma 3.9 cannot be applied. Lemma 3.6's convexity computation, by contrast, checks out; the issue is in the preceding lemma.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies deterministic distributed algorithms for the Lovász Local Lemma under the exponential criterion p2^d < 1. It establishes a sharp threshold at p = 2^{-d}: for variables affecting at most two events it gives an O(d + log* n) deterministic LOCAL algorithm matching the known Ω(log* n) lower bound, and for variables affecting at most three events it gives an O(d^2 + log* n) deterministic algorithm under the same criterion. The rank-3 proof maintains an invariant P* on edge-endpoint labels of the dependency graph; the core technical step is showing that the set of representable probability-increase triples is incurved, which is reduced to an explicit characterization of that set and a convexity computation. The authors conjecture that the same threshold holds for any number r of events affected by a variable.","tokens_in":18973,"tokens_out":24070,"duration_ms":245396,"significance":"If the proof is completed, the result is significant: it gives the first sharp exponential threshold for deterministic distributed LLL and improves on prior randomized algorithms for rank-3 variables. The rank-2 argument is clean and self-contained, and the rank-3 framework—representable triples, incurvedness, and the evil-value contrapositive—is an elegant reduction of an algorithmic question to a two-variable analytic statement. The construction has no fitted parameters, and the lower-bound side relies on separate published results, so the claimed sharpness is grounded in external theorems rather than built into the algorithm.","major_comments":[{"comment":"The displayed quadratic formula for the stationary points of c(x) is incorrect: for the equation x^2 - px + p = 0 the roots are (p ± sqrt(p^2 - 4p))/2, not p/2 ± sqrt(p^2 - 4p)/4. As printed, for the valid pair (a,b) = (1,2) the point called x1 lies outside the feasible interval [a/2, 2-b/2] = [1/2,1] and c(x1) does not equal f(1,2) = 2 - sqrt(3), so the proof as written does not identify the maximizing x. Since Lemma 3.5 is the characterization of S_rep used in Lemma 3.7 and hence in the Variable Fixing Lemma, this gap must be repaired; the subsequent algebra suggests that the intended root with the denominator 2 is correct, but the derivation and the case analysis for which root is feasible need to be rewritten.","section":"Appendix A, proof of Lemma 3.5"},{"comment":"The reduction from rank-2 to rank-3 variables by adding a 'virtual third affected bad event' is not justified. If a new event is added for a rank-2 variable, it shares that variable with the two original events, so the new event must be a node adjacent to them in the dependency graph; doing this for many rank-2 variables can increase the maximum degree d of the original events, and the hypothesis p2^d < 1 does not survive the transformation. In addition, a virtual event whose probability does not depend on the variable would remain a real (possibly occurring) event at the end of the algorithm, so it cannot be treated as an ordinary bad event in the final probability argument. Please either supply a degree-preserving reduction or state and prove a direct variable-fixing lemma for rank-2 variables; the weighted version of the rank-2 argument mentioned in Section 3.1 would suffice.","section":"Section 3, first paragraph"},{"comment":"The identity sum_{i=1}^k p_i Inc(x,y_i) = 1 used in the proof of Lemma 3.9 is asserted for each affected event x, but it requires Pr[E_x | theta] > 0. The definition of Inc explicitly sets Inc(x,y) = 0 when this denominator is zero, and in that case the identity is false. The convex-combination construction of the triples s_i therefore collapses if any of the three events has conditional probability zero. This case is not excluded by P*, since P* only gives an upper bound on the conditional probability. Please handle zero-probability events separately (for example, by dropping the corresponding coordinate from the triple) or justify the identity by a limiting argument.","section":"Section 3.3, proof of Lemma 3.9"}],"minor_comments":[{"comment":"The set-builder notation '{(a,b,c) ⊆ R^3_{\\ge 0} | ...}' should use the membership symbol '\\in' instead of '\\subseteq'.","section":"Lemma 3.5, statement"},{"comment":"In the case a,b ≠ 0, the claim that x2 is outside the feasible interval is only verified with the incorrect formula; after correcting the root formula, the two cases a > b and b > a must be handled explicitly, since the labeling of which root is feasible flips depending on the sign of a-b.","section":"Appendix A, proof of Lemma 3.5"},{"comment":"The reference [VG19] has garbled author names ('Vclav Rozho' should be 'Václav Rozhoň'); please fix the spelling and the title formatting.","section":"Section 1, Related Work and References"},{"comment":"There is a typo 'assoiciated' in the discussion of the case r > 3; please correct it.","section":"Section 1, Techniques and Generalization"},{"comment":"The caption refers to the 'orange shaded surface'; if the figure is printed in grayscale, the shading may be difficult to distinguish, so please add a pattern or explicit labeling.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The core idea of the paper appears sound and the rank-2 contribution is clean, but the proof of the rank-3 theorem as written contains a wrong root formula in a load-bearing lemma and an unjustified reduction for rank-2 variables. Both issues seem repairable within the manuscript's scope, but they require a careful revision rather than a simple edit. I recommend major revision and would be willing to re-review the revised appendix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, this paper has a genuinely new result: a deterministic O(d^2 + log* n) LOCAL algorithm for LLL under p < 2^-d when each variable affects at most three events, plus a sharp threshold at p = 2^-d when combined with known lower bounds. The rank-2 warm-up is Ghaffari's, and they say so. The rank-3 analysis - representable triples, incurvedness, the variable fixing lemma - is the real contribution. Second, the appendix has a concrete algebraic error in the proof of Lemma 3.5. The stationary points of c(x) are printed with the quadratic formula denominator wrong (4 instead of 2). For a=1, b=2, the printed \"maximizer\" is outside the feasible interval and gives c ≈ 3.76, not f(1,2) ≈ 0.268. So the characterization of S_rep is not established as written. The paper's derivative is correct, but the root formula that follows is not. This is fixable - the correct root recovers the stated f - but it needs to be corrected.\n\nThe reader's report flagged a second gap: Lemma 3.9 breaks when one of the three events already has conditional probability zero, because the sum identity sum p_i Inc(x,y_i)=1 fails. That is also real and also fixable: the averaged triple simply has a 0 where the dead event sits, and downward closure of S_rep puts it back in the set. Neither flaw looks load-bearing for the main theorem.\n\nWhat is good: the proof structure is honest. Lemma 3.6's Hessian computation checks out, the rank-2 argument is clean, and the paper is explicit about what generalizes to r>3 and what does not. The lower bounds that yield the threshold are published work, including the authors' own, cited properly. No fitted parameters, no circularity.\n\nThe weaknesses are proportional: the appendix is sloppy, and the zero-probability case is handled by a definition that silently breaks the identity. A referee should demand a rewrite of Appendix A and a clean treatment of zero-probability events. That is the right level of concern.\n\nWho is this for: people working on distributed LLL, LOCAL-model complexity, and derandomization. If the fixes are made, this becomes a significant reference. I would send it to a serious venue. It deserves rigorous peer review, not a desk reject.","headline":"A strong paper with a real but fixable algebraic error in a deferred proof; the rank-3 algorithm and threshold result deserve a serious referee.","tokens_in":19594,"tokens_out":10921,"would_cite":true,"duration_ms":85316,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"For the Lovász Local Lemma with variables affecting at most three events, a deterministic distributed algorithm runs in O(d^2 + log* n) rounds whenever p < 2^{-d}, making p = 2^{-d} a sharp threshold.","keywords":["Lovász Local Lemma","distributed algorithms","LOCAL model","deterministic algorithms","sharp threshold","probabilistic method","hypergraph orientation","derandomization"],"falsifier":"Recompute the Hessian matrix of $f$ at an interior point of $\\{(a,b): a+b<4\\}$ and check whether it has a negative eigenvalue; since Lemma 3.6 asserts positive definiteness everywhere on that open domain, a single such point -- or, equivalently, two non-representable triples whose convex combination is representable -- would falsify the geometric core of the proof.","tokens_in":18431,"feed_emoji":"⚡","tokens_out":13788,"duration_ms":117616,"temperature":0.7,"pith_summary":"This paper tries to pin down exactly when the Lovász Local Lemma (LLL) becomes easy to solve on a distributed network. It proves that for the case where each random variable influences at most two bad events, and then for the harder case of at most three events, the exponential criterion $p < 2^{-d}$ is a sharp threshold: below it there is a deterministic LOCAL algorithm that runs in $O(d + \\log^* n)$ rounds (rank 2) or $O(d^2 + \\log^* n)$ rounds (rank 3), matching the universal $\\Omega(\\log^* n)$ lower bound, while at $p \\geq 2^{-d}$ the known $\\Omega(\\log \\log n)$ randomized and $\\Omega(\\log n)$ deterministic lower bounds take over. Because the fixing process works in any adversarial order and only consults the 1-hop neighborhood, the result gives deterministic algorithms for concrete problems such as rank-3 hypergraph orientation. The paper also conjectures the same threshold holds for variables affecting any fixed number $r$ of events, and provides a proof framework where almost all steps already extend to arbitrary $r$.","feed_headline":"Lovász Local Lemma hits sharp threshold at p = 2^{-d}","feed_subtitle":"Below that probability, deterministic distributed algorithms run in O(d^2 + log* n) rounds; above it, lower bounds jump.","key_machinery":"The engine is the Variable Fixing Lemma (Lemma 3.2), supported by a bookkeeping scheme called property $\\mathcal{P}^*$. The algorithm maintains, on every edge of the dependency graph and for each endpoint, a value in $[0,2]$ whose product over the incident edges upper-bounds the conditional probability of that endpoint's bad event, and the values on any edge always sum to at most 2. When a rank-3 variable on hyperedge $\\{u,v,w\\}$ is fixed, the lemma guarantees a choice of value and an update of the six edge values that preserves $\\mathcal{P}^*$. The geometric core is the set $S_{\\mathrm{rep}}$ of representable triples $(a,b,c)$ -- triples of probability increases that can be absorbed by the three edges of a triangle -- which is characterized as the region under the surface $f(a,b) = 4 + \\frac{1}{2}(ab - 2a - 2b - \\sqrt{ab(4-a)(4-b)})$. The proof reduces existence of a good fixing choice to the incurredness of $S_{\\mathrm{rep}}$ (no convex combination of two non-representable triples is representable), and incurredness is derived from convexity of $f$ on $\\{a+b \\le 4\\}$, verified by a Hessian computation.","core_discovery":"The central claim is Theorem 1.3: for an LLL instance satisfying $p2^d < 1$ in which every random variable affects at most three bad events, there is a sequential and local deterministic process that assigns values to all variables and avoids every bad event. Local means the choice for each variable depends only on the 1-hop neighborhood in the dependency graph, so the process can be parallelized: after a 2-hop coloring with $O(d^2)$ colors (computable in $\\tilde{O}(d) + \\log^* n$ rounds), iterating through the color classes gives an $O(d^2 + \\log^* n)$-round deterministic LOCAL algorithm (Corollary 1.4). Together with known lower bounds for $p \\geq 2^{-d}$, this makes $p = 2^{-d}$ a sharp threshold for variables affecting up to three events, the same spot as the rank-2 case, and is the paper's evidence for Conjecture 1.5 that the threshold is independent of $r$.","pith_inferences":["If the threshold phenomenon holds for every $r$ as Conjecture 1.5 predicts, the distributed complexity of LLL would be governed by the exponential criterion alone; changing $r$ would only affect the polynomial dependence on $d$, not the $\\log^* n$ term.","The geometric reduction suggests a testable route to the conjecture: for $r=4$ one could numerically search for pairs of non-representable tuples whose convex combination is representable; finding one would show where the framework breaks, and failing to find one would support the pattern.","Because the fixing order is adversarial and the bookkeeping is purely local, the construction acts as a deterministic derandomization of the resampling pipeline under a local probability bound; obtaining a similar result for criteria weaker than $p < 2^{-d}$ would probably require a different invariant.","The weak-splitting applications hint that the same technique could eventually attack the original weak splitting problem, whose efficient solution would imply efficient deterministic algorithms for maximal independent set and maximum-degree-plus-one vertex coloring."],"forward_implications":["For rank-2 and rank-3 instances, $p < 2^{-d}$ admits deterministic distributed algorithms with $O(d + \\log^* n)$ and $O(d^2 + \\log^* n)$ rounds respectively, matching the $\\Omega(\\log^* n)$ lower bound on constant-degree graphs.","At $p = 2^{-d}$ and above, no algorithm can beat $\\Omega(\\log \\log n)$ rounds (randomized) or $\\Omega(\\log n)$ rounds (deterministic), so the jump across the threshold is not an artifact of the algorithm.","The deterministic rank-3 algorithm improves on the previous best randomized algorithm for this regime, whose runtime was super-polylogarithmic.","The same fixing process yields deterministic algorithms for applications such as orientation in rank-3 hypergraphs and a weak splitting variant with 16 colors where every node sees at least 2 colors.","Almost all proof steps generalize to arbitrary $r$; only the convexity of the analogous surface is left open, which is the gap to Conjecture 1.5."],"supporting_citations":[{"why":"Formulates the Lovász Local Lemma whose existence guarantee is the problem being algorithmically solved.","marker":"[EL74]"},{"why":"Gives the resampling algorithm that is the baseline distributed LLL method the paper's deterministic process aims to improve upon.","marker":"[MT10]"},{"why":"Supplies the $\\Omega(\\log \\log n)$ randomized lower bound at $p \\geq 2^{-d}$, pinning down the high side of the threshold.","marker":"[BFH+16]"},{"why":"Supplies the $\\Omega(\\log n)$ deterministic lower bound at $p \\geq 2^{-d}$.","marker":"[CKP16]"},{"why":"Gives the $\\Omega(\\log^* n)$ lower bound for any criterion that depends only on $d$, proving the paper's $O(\\log^* n)$ algorithms are optimal.","marker":"[CPS17]"},{"why":"Provides the $O(d + \\log^* n)$ edge-coloring used to parallelize the rank-2 fixing process.","marker":"[PR01]"},{"why":"Provides the 2-hop vertex coloring with $O(d^2)$ colors in $\\tilde{O}(d) + \\log^* n$ rounds used in the rank-3 parallelization.","marker":"[FHK16]"},{"why":"Supplies the Hessian positive-semidefiniteness criterion used to prove Lemma 3.6, the convexity of $f$.","marker":"[BV04]"}],"fun_headline_variants":["LLL sharp threshold at p=2^{-d} for up to 3 events per variable","Deterministic LLL algorithm: O(d^2+log* n) rounds below p=2^{-d}","LLL threshold at p=2^{-d} extends to r=3 case","LLL threshold at p=2^{-d} holds for 3-event variables"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The rank-3 result stands on the analytic claim that $f(a,b) = 4 + \\frac{1}{2}(ab - 2a - 2b - \\sqrt{ab(4-a)(4-b)})$ is convex on the triangle $a+b \\le 4$; if that Hessian computation fails, the Variable Fixing Lemma and the threshold theorem lose their foundation.","fun_headline_variants_meta":{"raw":{"variants":["LLL sharp threshold at p=2^{-d} for up to 3 events per variable","Deterministic LLL algorithm: O(d^2+log* n) rounds below p=2^{-d}","LLL threshold at p=2^{-d} extends to r=3 case","LLL threshold at p=2^{-d} holds for 3-event variables"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001322,"raw_usage":{"total_tokens":5463,"prompt_tokens":1105,"completion_tokens":4358,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":721,"completion_tokens_details":{"reasoning_tokens":4270}},"tokens_in":721,"tokens_out":4358,"duration_ms":30570,"temperature":1.0,"reasoning_tokens":4270,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:52:09.920187+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the Hessian matrix of $f$ at an interior point of $\\{(a,b): a+b<4\\}$ and check whether it has a negative eigenvalue; since Lemma 3.6 asserts positive definiteness everywhere on that open domain, a single such point -- or, equivalently, two non-representable triples whose convex combination is representable -- would falsify the geometric core of the proof.","supporting_citations":[],"review_version":1}