{"id":"d47801e6-34dd-4088-90ce-2803625aec26","arxiv_id":"2607.25059","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"Solver-free parallel spectral sparsification via LDD-based robust-connectivity estimates achieves O(m log n log nW) work and O(log² n log* n) depth with no ε factor in either resource.","lead":"A parallel algorithm builds spectral sparsifiers of weighted graphs using only low-diameter decompositions and edge sampling, with work and depth independent of the accuracy parameter ε. That removes a long-standing bottleneck for solver-free parallel Laplacian preconditioning and approximate Cholesky.","discovery_kind":"new_method","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"The reader's flagged Claim 2.8 domination is actually sound; the real gap is that Lemma 2.5 (imported from Kapralov–Panigrahy) is false as stated without a min-weight normalization, and Algorithm 2 then leaves bq(e) undefined for exactly the edges that violate it.","rationale":"The reader identified the right neighborhood (the Claim 2.8–2.10 / Lemma 3.1 chain) but the specific domination step they flagged survives scrutiny, including the weighted min{wπ,1} sampling and the boundary case. The sharper, load-bearing issue is one step earlier in the chain: Lemma 2.5 is imported from Kapralov–Panigrahy without its (presumably present) min-weight hypothesis, and the paper states Theorem 3.4 for arbitrary weighted graphs. A tiny-weight bridge makes Lemma 2.5 false, simultaneously exposing the undefined-j_e corner in Algorithm 2's line 8. This is a real correctness gap in the theorem as stated, but it is patched by a standard one-line normalization (min weight 1, or weight-ratio in place of W), under which I verified the whole chain closes — including that every edge then lands in Ẽ(0) w.h.p., removing the empty-set case. That profile — genuine hole, trivial standard fix — is exactly what CONDITIONAL is for, so I do not move the reader's verdict; I would add \"state the weight normalization and the j_e default\" to the conditions. Agreement is partial: same region of the proof, different specific weak point.","tokens_in":18227,"tokens_out":12812,"duration_ms":462119,"concrete_test":"Analytic, no simulation needed: take G = two unit-weight triangles joined by a bridge e of weight ε = 10^{-6}, n = 6, κ = Θ(log n). (1) Compute q_κ(e) exactly: p_κ(e,η) = 1 - εη ≥ 1/2 for all η ∈ [0,1], so q_κ(e) = 1; then Lemma 2.5 demands R_e = 10^6 ≤ 2κ, which is false — confirming the lemma needs w_e ≥ 1. (2) Check the original source [8] Lemma 2 for a min-weight hypothesis. (3) Trace Algorithm 2 on this graph: verify e ∉ Ẽ(i) for all i w.h.p. (Z_e ≈ 0), so j_e is undefined, and confirm that no default value ≤ 1 makes p_e ≥ c·w_e R_e log n/ε². If the paper adds \"w.l.o.g. w_e ≥ 1\" (or replaces W by W/w_min in the search range and work bound), re-run the trace: e ∈ Ẽ(0) w.h.p. and the chain closes.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I first checked the reader's weakest assumption. Claim 2.8's stochastic domination holds: for the union H of two copies of G_{π/4}, Pr[f∈H] = 1-(1-p'_f)² ≤ min(2p'_f, 1) ≤ min{w_f π, 1} in all cases (when p'_f = 1, w_f π ≥ 4 so the RHS is 1), and edgewise independence gives the monotone coupling. The boundary case q_κ(e) = π/4 is fine by continuity of p_κ in η. The constants in Lemma 3.1 also check out: (31/32)(9/16) = 279/512 > 8.5/16 > 33/64 = (33/32)(1/2), and the non-standard Chernoff variant (Thm 2.2 part 2) is valid since ((1+δ)c-μ)²/μ ≥ δ²c for μ ≤ c.\n\nThe actual soft spot is Lemma 2.5, quoted as \"Lemma 2 in [8]\": R_e ≤ 2κ·q_κ(e), with no weight restriction anywhere in the paper (W is defined as max weight only). Counterexample: let e be a bridge of weight ε < 1/(2κ). In G_η, e appears w.p. min{εη,1} = εη, so p_κ(e,η) = 1-εη ≥ 1/2 for all η ∈ [0,1], giving q_κ(e) = 1 — while R_e = 1/ε > 2κ. Lemma 2.5 fails. KP12 presumably assume w_e ≥ 1 (consistent with this paper's experiments, min weight 1, and with the log nW work bound, which should otherwise be log of the weight ratio). The failure propagates concretely: for this edge, Item 2 of Lemma 3.1 never guarantees inclusion (q_κ = 1 > π_i/4 always) and Item 1 excludes it everywhere (q_{4κα} = 1 ≥ π_i), so j_e = max{i : e ∈ Ẽ(i)} in Algorithm 2 line 8 is empty and bq(e) is undefined; any default ≤ 1 gives bR_e ≤ 8κα_LDD ≪ R_e, so the leverage-score-1 bridge is undersampled and Theorem 2.1's hypothesis fails. Note that with w_e ≥ 1 both gaps close simultaneously: e ∈ G_{π_0} = G_1 w.p. 1, dist(u,v) = 1 ≤ κ, so e ∈ Ẽ(0) w.h.p. So the theorem needs one unstated line — min-weight normalization — without which the stated correctness claim has a genuine hole.","agreement_with_reader":"partial"},"referee_report":{"model":"moonshotai/kimi-k3","summary":"The paper presents a solver-free parallel algorithm for spectral sparsification of weighted graphs. Following Kapralov–Panigrahy (KP12), edges are sampled according to (over-estimates of) their robust connectivities q_κ(e). The new technical contribution is a method for estimating q_κ(e) that replaces approximate distance oracles by low-diameter decompositions (LDDs): for O(log nW) geometrically spaced sampling rates π, the algorithm samples t = O(log n) copies of G_π, runs a parallel LDD on each, and uses the fraction of trials in which an edge's endpoints share a cluster as a decision statistic Z_e. Lemma 3.1 shows the threshold 8.5/16 separates the regimes q_κ(e) ≤ π/4 and q_{4κα_LDD}(e) ≥ π w.h.p.; a binary search (Lemma 3.2) yields q̂(e) with q_{4κα_LDD}(e) ≤ q̂(e) ≤ 8q_κ(e); Lemma 3.3 converts these to effective-resistance over-estimates with total weight O(n log² n); Theorem 3.4 then applies Spielman–Srivastava sampling to obtain a (1±ε) sparsifier with O(n ε^{-2} log³ n) edges in work O(m log n log nW) and depth O(log² n log* n), with no ε-dependence in the estimation phase. Experiments on eliminated 2D/3D grid graphs show a heuristic variant (max-score spanning tree backbone plus budgeted leverage sampling) beating weight-based baselines by 4–5× in PCG iterations. I verified the new technical pieces: Claim 2.8's stochastic domination holds (Pr[f ∈ H] = 1-(1-p'_f)² ≤ min{w_f π, 1} in all cases, with edgewise independence giving the monotone coupling; the boundary q_κ(","tokens_in":18904,"tokens_out":7102,"duration_ms":236700,"significance":"If the normalization gap (Major Comment 1) is fixed, this is a strong contribution. It gives the first solver-free parallel spectral sparsification algorithm whose estimation work and depth carry no ε^{-2} factor — an asymptotic and conceptual improvement over Koutis (2014) and its refinements, and a clean plug-in for the parallel approximate-Cholesky framework of [3]. The two structural insights (distance estimation is only needed at a two-scale threshold; an LDD same-cluster indicator is correct in expectation, avoiding a log-factor amplification) are simple, well motivated, and likely reusable. The paper also ships a working parallel implementation on GBBS with experiments showing 4-5× improvements in PCG iteration counts over weight-based baselines at matched edge budgets, with wall-clock data in Appendix A.2 supporting the iteration-count proxy. The result is falsifiable, the analysis is largely self-contained, and the constants are explicit. I note explicitly that the stress-test concern about Claim 2.8 does not land; the genuinely soft point is the imported Lemma 2.5, not the new material.","major_comments":[{"comment":"Lemma 2.5 is quoted from [8] as R_e <= 2κ·q_κ(e) with no weight restriction, but as stated it is false, and the failure propagates into the main theorem. Counterexample: let e be a bridge of weight ε < 1/(2κ). Since the only u-v path is e itself, p_κ(e,η) = 1 - εη >= 1/2 for all η in [0,1], so q_κ(e) = 1, while R_e = 1/ε > 2κ. Kapralov-Panigrahy require a unit-minimum-weight normalization (consistent with this paper's experiments, min weight 1, and with the log nW work bound, which otherwise should be a log of the weight ratio). The failure is not cosmetic: for such an edge, Item 2 of Lemma 3.1 never guarantees inclusion (q_κ = 1 > π_i/4 for all i) and Item 1 forces exclusion everywhere, so j_e = max{i : e in Ẽ(i)} in Algorithm 2, line 8 is empty and bq(e) — hence bR_e — is undefined; any default <= 1 gives bR_e <= 8κα_LDD << R_e = 1/ε, so this leverage-score-1 edge is undersampled and t","section":"Lemma 2.5 (§2.2), Algorithm 2 line 8, Theorem 3.4"},{"comment":"Even after imposing the normalization w_e >= 1, the proof of Lemma 3.2 silently assumes j_e exists for every edge, and this need not hold: an edge with q_κ(e) > 1/4 and q_{4κα_LDD}(e) < 1 falls in the gap region of Algorithm 1 at every π_i (Item 2 never forces inclusion, Item 1 only forces exclusion at small π_i), so it can be excluded from all Ẽ(i), leaving j_e and bq(e) undefined. A one-line fix suffices — e.g., set bq(e) = 1 (equivalently j_e = -1 with π = 2) for such edges, which is a valid over-estimate since R_e <= 2κ·q_κ(e) <= 2κ <= 8κα_LDD·1 — but the algorithm and the proof currently do not specify any default, and the claimed guarantee bR_e >= R_e in Lemma 3.3 has no content for edges where bR_e is undefined. Please add the default rule and the two-sentence argument that it preserves both bounds of Lemma 3.3.","section":"Lemma 3.2 / Algorithm 2, lines 7-11"},{"comment":"The abstract and §1 claim the algorithm 'eliminates any dependence on the target approximation accuracy ε in the algorithm's work and depth.' This is literally false for the total work: the output itself has Θ(n ε^{-2} log^3 n) edges in expectation, so writing the sparsifier costs Ω(n ε^{-2}) work (capped at m). The correct and still strong statement is that the ε^{-2} factor appears only in the output size and the final independent-sampling step, not as a multiplicative overhead in the estimation work/depth — in contrast to [9,13], whose work and depth scale with ε^{-2}. As written, a reader comparing against Theorem 3.4's stated work bound O(m log n log nW) will notice the discrepancy. Please qualify the claim in the abstract, §1, and the 'Our Contribution' paragraph.","section":"Abstract, §1, Theorem 3.4"}],"minor_comments":[{"comment":"Broken cross-references: the proofs contain '??2.10' (proof of Lemma 3.1), '??2.8' (Lemma 3.1), and '??2.7' (Lemma 3.2). Also inconsistent capitalization of 'algorithm 1'/'theorem 2.1' versus 'Algorithm 2'/'Theorem 3.4' throughout.","section":"Proofs of Lemmas 3.1, 3.2"},{"comment":"Notation collisions: κ denotes the condition number in §1 and the robust-connectivity parameter from Definition 2.3 onward; c denotes the generic constant in Theorem 2.2 and the oversampling constant of Theorem 2.1 (Algorithm 2, line 14). Consider renaming one of each pair.","section":"§1 vs §2.2; Theorem 2.2"},{"comment":"Tables 1 and 2: the 'Unif.' column is entirely em dashes and the 'Lev.' column has starred failures; a one-line explanation that uniform (and often pure leverage-score) sampling disconnects the graph, driving the condition number to infinity, would save readers from inferring a data error.","section":"Tables 1-2 (§4.5.1)"},{"comment":"Remark 4.1 concludes a '1/2-approximate spectral sparsifier'; state explicitly that this corresponds to instantiating Theorem 2.1 at ε = 1/2 and give the resulting constant c_1 relation.","section":"Remark 4.1"},{"comment":"§5 states that the algorithm 'immediately improves the depth and work of the parallelization framework' of [3]; an explicit corollary with the resulting work/depth numbers for parallel approximate Cholesky would make this application claim checkable.","section":"§5"},{"comment":"After the normalization fix (Major Comment 1), define the weight ratio (e.g., W_ratio = w_max/w_min) in the Notation paragraph; W is currently defined as max weight only, and Claim 2.7's bound 1/(4mW) should be restated accordingly.","section":"§2 Notation; Claim 2.7"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a clean fit for the journal's scope and, conditional on the normalization fix in Major Comment 1, I would expect to support acceptance. The flagged error is in an imported lemma rather than in the paper's new technical contributions, which I verified independently; the fix is standard but must be made explicit because Theorem 3.4 as stated is incorrect for graphs with sub-unit edge weights. The citation pattern is unremarkable; the authors appropriately acknowledge the competing [12]+[8] route. No concerns beyond the technical points in the report."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The real news is a solver-free parallel sparsifier whose work and depth no longer depend on ε. That is the first such improvement since Koutis 2014, and it directly helps the parallel approximate-Cholesky setting where you repeatedly sparsify to ε/log n.\n\nWhat is new is simple and clean: estimate Kapralov–Panigrahy robust connectivities by independent edge subsampling plus one LDD per sample, then binary-search over O(log nW) scales. You only need expectation-level separation of short versus long distances, so a single LDD indicator plus Chernoff on O(log n) trials suffices. The reduction chain (Claims 2.7–2.8, Lemma 3.1, binary search, resistance oversampling, Thm 3.4) is easy to follow and the resource bounds are stated tightly. Experiments on grid fill-in show the practical max-tree + leverage heuristic beating weight-based baselines by roughly 4–5× in PCG iterations at fixed budget; that is useful evidence even if the graphs are narrow.\n\nOne soft spot is real but fixable. Lemma 2.5 is quoted from KP12 as R_e ≤ 2κ q_κ(e) with no weight restriction. A bridge of weight ε ≪ 1/κ has q_κ = 1 while R_e = 1/ε, so the inequality fails and Algorithm 2 can leave bq(e) undefined (or far too small). The paper’s experiments use min weight 1 and the log nW work bound is consistent with an implicit unit-weight (or min-weight-normalized) setting; adding that one line closes both the lemma and the undefined-estimate case. Constants (α_LDD, κ, the 8.5/16 threshold) stay asymptotic, and the practical algorithm is only conditionally guaranteed, but neither undercuts the main claim once weights are normalized. Citation pattern is appropriate; no circularity.\n\nThis is for people who care about parallel Laplacian primitives and black-box sparsifiers inside solvers. The math is serious, the gap is minor and local, and a referee should see it. I would cite the LDD estimator and the ε-free bounds.","headline":"Solid LDD-based estimator that really removes ε from work/depth; one unstated min-weight normalization is needed for the imported resistance bound, but the core idea is clean and worth engaging.","tokens_in":20047,"tokens_out":555,"would_cite":true,"duration_ms":11158,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W10","05C85","68R10","65F08"],"pacs":[],"model":"grok-4.5","headline":"A parallel spectral sparsifier built only from low-diameter decompositions removes all dependence on accuracy ε from work and depth.","keywords":["spectral sparsification","low-diameter decomposition","robust connectivity","parallel algorithms","effective resistance","Laplacian preconditioning","solver-free"],"falsifier":"Run the decide procedure on a family of graphs with known robust connectivities (or exact effective resistances) and check whether the empirical same-cluster frequencies still fall cleanly above 8.5/16 precisely when q_κ(e) ≤ π/4 and below it when q_{4κα_LDD}(e) ≥ π; a systematic misclassification at moderate n would refute the lemma.","tokens_in":19449,"feed_emoji":"🕸️","tokens_out":1103,"duration_ms":23115,"temperature":0.7,"pith_summary":"Spectral sparsifiers replace a dense weighted graph by a much sparser one that still approximates every quadratic form of the Laplacian, which is the key primitive behind fast Laplacian solvers and parallel approximate Cholesky. Prior solver-free parallel methods either needed heavy distance oracles or paid an ε⁻² factor in both work and depth, which becomes costly when the target accuracy is 1/log n. This paper shows that robust connectivities—probabilities that two endpoints stay close after random edge sub-sampling—can be estimated by running ordinary low-diameter decompositions on a logarithmic number of independently thinned copies of the graph. Edges whose endpoints repeatedly land in the same cluster receive small sampling probabilities; the rest are kept more often. The resulting algorithm produces a (1±ε)-sparsifier with O(n ε⁻² log³ n) edges in work O(m log n log(nW)) and depth O(log² n log* n), with no ε factor in the resource bounds. Experiments on grid Laplacians after partial Cholesky fill-in show the practical leverage-score heuristic cuts PCG iterations by roughly 4–5× versus weight-based baselines at the same edge budget.","feed_headline":"LDD sampling builds spectral sparsifiers with no ε cost","feed_subtitle":"Work and depth stay free of the accuracy parameter, speeding parallel Laplacian solvers","key_machinery":"The Robust Connectivity Decide procedure (Algorithm 1 / Lemma 3.1): for a candidate density π it runs O(log n) LDDs on independent copies of G_π and keeps an edge when the fraction of trials in which its endpoints share a cluster exceeds 8.5/16; this cleanly separates edges with q_κ(e) ≤ π/4 from those with q_{4κα_LDD}(e) ≥ π, enabling a geometric search for usable resistance overestimates.","core_discovery":"Robust connectivities of a weighted graph can be estimated well enough for spectral sparsification by nothing more than independent edge sub-sampling and parallel low-diameter decompositions: if endpoints often share an LDD cluster across O(log n) thinned copies at geometrically decreasing densities, the edge’s robust connectivity (hence an upper bound on its effective resistance) is small, and sampling according to those estimates yields a (1±ε) sparsifier whose construction work and depth are independent of ε.","pith_inferences":["Dynamic or batch-dynamic LDD data structures would likely turn the same estimator into a parallel batch-dynamic sparsifier, a direction the authors flag but do not develop.","The ε-independence makes the method especially attractive inside nested dissection or multilevel schemes that repeatedly request finer and finer sparsifiers.","If the same cluster-frequency statistic can be shown to control directed or Eulerian effective resistances, the technique might extend to the directed Laplacian setting where practical sparsifiers are still scarce."],"forward_implications":["Parallel approximate-Cholesky frameworks that call a black-box sparsifier O(log n) times at accuracy ε/log n no longer inherit an extra ε⁻² (hence log² n) blow-up in depth or work.","Any downstream routine whose bottleneck was solver-free parallel sparsification can now treat work and depth as essentially independent of the final approximation quality.","The same LDD-based estimator supplies the scores for a practical one-shot max-tree-plus-leverage sparsifier that measurably reduces PCG iterations on filled-in grid Laplacians.","Because the only primitives are LDDs, MSTs and independent sampling, the construction is immediately portable to existing parallel graph libraries."],"fun_headline_variants":["LDD overlaps estimate robust connectivity for ε-free sparsifiers","Solver-free parallel sparsification with no ε in work or depth","Subsample then LDD: spectral sparsifiers independent of ε","Robust connectivities via LDD clusters enable ε-free sparsifiers","Parallel LDDs on thinned graphs build sparsifiers without ε cost"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The method needs the probability that two nearby vertices land in the same low-diameter cluster, and the probability that two far vertices do not, to sit on opposite sides of a fixed numerical threshold after a constant number of random thinnings; if real LDD diameters or the two-copy coupling are much worse than the analysis assumes, the separation fails.","fun_headline_variants_meta":{"raw":{"variants":["LDD overlaps estimate robust connectivity for ε-free sparsifiers","Solver-free parallel sparsification with no ε in work or depth","Subsample then LDD: spectral sparsifiers independent of ε","Robust connectivities via LDD clusters enable ε-free sparsifiers","Parallel LDDs on thinned graphs build sparsifiers without ε cost"]},"model":"grok-4.5","effort":"low","cost_usd":0.004105,"raw_usage":{"total_tokens":1304,"prompt_tokens":821,"num_sources_used":0,"completion_tokens":92,"cost_in_usd_ticks":41048000,"prompt_tokens_details":{"text_tokens":821,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":391,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":821,"tokens_out":92,"duration_ms":6942,"temperature":1.0,"reasoning_tokens":391,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T02:19:59.008769+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Run the decide procedure on a family of graphs with known robust connectivities (or exact effective resistances) and check whether the empirical same-cluster frequencies still fall cleanly above 8.5/16 precisely when q_κ(e) ≤ π/4 and below it when q_{4κα_LDD}(e) ≥ π; a systematic misclassification at moderate n would refute the lemma.","supporting_citations":[],"review_version":1}