{"id":"76bced64-efb6-483c-b227-7f378ea68ffa","arxiv_id":"2508.19898","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A CONGEST algorithm estimates graph conductance to a sqrt(2.01) factor in O(log^2 n / phi) rounds by approximating Laplacian eigenvalues with the power method.","lead":"This paper gives faster distributed algorithms that estimate how close a network is to having a sparse cut. The algorithms use simple repeated matrix-vector multiplications, improve the best known round counts, and also handle k-way cuts and weighted graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's guarantee is false: the proof incorrectly assumes λ2 ≤ φ in Cheeger's inequality, but λ2 can be 2φ (e.g., complete graph), so √(2λ2) exceeds √(2.01φ).","rationale":"The reader's strongest claim is Theorem 1, and the identified weakest assumption was the numerical stability analysis in Claim 2. However, the most load-bearing flaw is independent of that: the reduction from λ2 to φ uses Cheeger's inequality incorrectly, assuming λ2 ≤ φ when Cheeger gives λ2 ≤ 2φ. This is not a minor technicality; the guarantee √(2.01φ) is impossible for graphs like the complete graph, where λ2 ≈ 2φ. The output √(2λ2) then equals 2√φ, which exceeds √(2.01φ) for every φ>0. This invalidates the main theorem. The Claim 2 issue identified by the reader is real but secondary; even if repaired, the √(2.01φ) bound still fails. Therefore the paper's central contribution is not correct as stated, and the verdict should be REJECT rather than CONDITIONAL.","tokens_in":34375,"tokens_out":32031,"duration_ms":265803,"concrete_test":"Analytically compute the algorithm's output on K_n. For K_n, λ2 = n/(n-1) and φ = ceil(n/2)/(n-1). For n=100, λ2 ≈ 1.0101, φ ≈ 0.505, so the output √(2λ2) ≈ 1.4214, while √(2.01φ) ≈ 1.0075. The output exceeds the claimed upper bound. More generally, √(2λ2)/φ ≈ 2√2 > √(2.01/φ) for all φ>0, so the theorem fails whenever λ2 is close to the Cheeger upper bound.","verdict_should_be":"REJECT","load_bearing_attack":"The proof of Theorem 1 (Section 3.1) derives the claimed approximation by setting δ = 0.005φ and outputting φ̃ = √(2λ̃2). It states: φ̃ ≤ √(2λ2 + 2δ) ≤ √(2φ + 2δ). This last inequality requires λ2 ≤ φ. However, Cheeger's Inequality (Theorem 8 in the paper) gives only λ2 ≤ 2φ, and this factor of 2 is tight. For a complete graph K_n, φ ≈ 1/2 while λ2 = n/(n-1) ≈ 1, so λ2 ≈ 2φ. Then √(2λ2) ≈ √2 ≈ 1.414, whereas √(2.01φ) = √(1.005) ≈ 1.0025. The output violates the claimed upper bound. Since λ2 can be as large as 2φ for any φ>0, the √(2.01φ) guarantee is unattainable with the described spectral output. This is not a minor proof gap; it invalidates the central claim of the paper.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributed approximation of the sparsest cut (conductance) in the CONGEST model. The main claimed result (Theorem 1) is a randomized algorithm that, for an undirected weighted n-node graph with sparsest cut φ, outputs at every vertex a value φ̃ with φ ≤ φ̃ ≤ √(2.01φ) in O(log² n / φ) rounds. The algorithm works by approximating eigenvalues of the normalized Laplacian via a distributed power method, then applying Cheeger's inequality. The paper also claims a generalization to k-way conductance (Theorem 2), an eigenvalue-estimation theorem (Theorem 5), and LOCAL lower bounds for conductance and eigenvalue approximation (Theorems 3, 4, 6). The proofs rely on a power-method analysis with a bit-precision lemma, a perturbation analysis for the second eigenvalue, and higher-order Cheeger inequalities.","tokens_in":34685,"tokens_out":6993,"duration_ms":73169,"significance":"If the main theorem were correct, it would give a near-optimal (up to a logarithmic factor) spectral approximation of conductance in the CONGEST model, improving on previous expander-decomposition-based algorithms both in approximation quality and round complexity. The lower bounds are also of interest. The paper is generally well written, and the power-method implementation with bit-precision control is a useful contribution. However, the central sparsest-cut guarantee is not correct as stated, and the flaw is load-bearing rather than cosmetic.","major_comments":[{"comment":"The proof derives φ̃ = √(2λ̃2) and claims φ̃ ≤ √(2λ2 + 2δ) ≤ √(2φ + 2δ). The second inequality requires λ2 ≤ φ, but Cheeger's Inequality (Theorem 8) gives only λ2 ≤ 2φ, and this is tight. For the complete graph K_n, λ2 = n/(n−1) and φ = n/(2(n−1)), so λ2 = 2φ. With δ = 0.005φ, the output √(2λ̃2) can be as large as √(4.01φ) ≈ 2.0025√φ, while the claimed upper bound is √(2.01φ) ≈ 1.0025√φ. Thus the stated √(2.01φ) guarantee is false for the algorithm as described. The same error invalidates the claim of an additive ε approximation on the √(2φ) bound.","section":"Section 3.1, proof of Theorem 1"},{"comment":"The numerical-stability analysis for approximating λ2 asserts (2/(2−λ2))^l ≤ (1+λ2)^l without justification. This inequality is false when λ2 > 1; for example, if λ2 = 1.5 then 2/(2−λ2) = 4 > 2.5 = 1+λ2. Since λ2 can exceed 1 (e.g., near-bipartite graphs), the claimed polynomial error amplification is not established. The proof needs an explicit bound on λ2 (e.g., λ2 ≤ n/(n−1) or a separate treatment of near-bipartite graphs). This gap affects Theorem 13 and therefore the eigenvalue subroutine on which Theorem 1 depends.","section":"Section 2.4, Claim 2"},{"comment":"The paper states that 'the best possible approximation achievable through spectral methods is √(2φ)' and then claims to match this bound up to a 1.005 factor. But Cheeger's Inequality in the standard form gives λ2 ≤ 2φ, so a spectral output of √(2λ2) is at best √(4φ) = 2√φ. The claimed √(2φ) limit and the derived √(2.01φ) guarantee are inconsistent with the paper's own Theorem 8. This is not a minor typo; it reflects the central error in Theorem 1.","section":"Section 1.1 and 3.1, interpretation of Cheeger's Inequality"}],"minor_comments":[{"comment":"The proof contains dangling notation: '|⟨x0, ⟩| ≥ 3/16' is missing the eigenvector; it should be ⟨x0, vn⟩. Also, the variable i in x_i is used both for the iteration count and as an index in the spectral expansion, which is confusing.","section":"Section 2.4, Claim 2 proof"},{"comment":"The phrase 'the best possible approximation achievable through spectral methods is √2ϕ' is imprecise and contradicted by the paper's own Theorem 1. It should be clarified what is meant by 'approximation' here.","section":"Section 1.1"},{"comment":"There are repeated typos: 'sparest cut' should be 'sparsest cut'; 'sparsity1/n and 1/n2' should be formatted consistently.","section":"Section 3.3"},{"comment":"The proof uses x_i and x0 interchangeably in places; the notation should distinguish the vector before rounding from the original start vector. Also, the bound '||y|| ≤ δ||xi||' assumes componentwise rounding, which should be stated explicitly.","section":"Appendix A.2, Lemma 11 proof"}],"recommendation":"reject","confidential_remarks":"The flaw in Theorem 1 is not a local proof gap; the stated approximation factor is unattainable for the algorithm described, because Cheeger's Inequality only gives λ2 ≤ 2φ and the complete graph attains equality. A simple rescaling of the output cannot fix the issue, since the lower bound φ ≤ √(2λ2) forces the output scaling to be at least √2, while the upper bound would then exceed √(2.01φ) on K_n. The authors would need to weaken the main theorem to an O(√φ) bound, which is a substantially different contribution and would change the paper's abstract and framing. Given that the central advertised result is false, rejection is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things up front. The distributed power iteration machinery—CONGEST bit truncation, periodic orthogonalization, the k-way extension—is real and worth engaging with. But the headline sparsest-cut guarantee in Theorem 1 is not supported. The proof bounds φ̃ = √(2λ̃2) by √(2φ + 2δ), which requires λ2 ≤ φ. Cheeger's inequality gives λ2 ≤ 2φ, and that factor is tight: for K_n, φ ≈ 1/2 and λ2 = n/(n-1) ≈ 1. Then the output is roughly √(2λ2) ≈ √2 ≈ 1.41, while the claimed upper bound is √(2.01φ) ≈ √1.005 ≈ 1.0025. So the 2.01 guarantee is unattainable with the described spectral estimate. This is not a cosmetic typo; it is a load-bearing step in the main theorem. Setting δ = 0.005φ cannot fix it. A weaker O(√φ) bound with a larger constant may hold, and that would still be a meaningful improvement in some regimes, but it is not what is advertised.\n\nWhat is good: Section 2 is mostly careful and self-contained. Lemma 11, the bit-precision analysis, is nontrivial and a real contribution. The k-way eigenvalue approximation via approximate deflation is a sensible idea, and the LOCAL lower bounds are new. The paper also cites the relevant prior work (Kempe–McSherry in particular) honestly instead of inventing a strawman.\n\nThere is a second, smaller soft spot in Claim 2. The inequality (2/(2−λ2))^l ≤ (1+λ2)^l is false for λ2 > 1, and near-bipartite graphs make the left side huge; that stability lemma needs repair or an unstated spectral bound. The reader's conditional verdict caught this; the stress-test catches the bigger Theorem 1 problem. The two issues are separate and both real.\n\nNet: this is a paper with a plausible algorithmic core and a broken headline claim. It deserves a serious referee because the techniques are salvageable and the lower bounds likely stand, but I would not accept the current version. If I were the editor, I would send it out with the expectation of major revision: fix the numerical stability lemma, restate Theorem 1 with a correct constant or a different algorithm, and check whether the complexity claims still make sense under the corrected guarantee.","headline":"The eigenvalue-estimation machinery is real, but Theorem 1's √(2.01φ) guarantee is unsupported—the proof uses λ2≤φ, which Cheeger does not give and which fails for complete graphs.","tokens_in":35131,"tokens_out":10727,"would_cite":false,"duration_ms":117314,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"Distributed spectral method approximates sparsest cut to Cheeger-limit quality in O(log² n/φ) rounds.","keywords":["sparsest cut","conductance","normalized Laplacian","eigenvalue estimation","CONGEST model","power method","Cheeger's inequality","k-way conductance"],"falsifier":"Take a complete graph K_n, where λ2 = n/(n−1) > 1, and run the CONGEST λ2-estimation algorithm with the stated rounding and periodic re-orthogonalization over l = Θ(log n/λ2) iterations. If the Rayleigh quotient drifts by more than n^{-Θ(1)} or stops tracking µ_{n-1}, the numerical-stability step is false and the claimed O(log² n/φ) bound collapses on that family.","tokens_in":34315,"feed_emoji":"✂️","tokens_out":9044,"duration_ms":101263,"temperature":0.7,"pith_summary":"This paper shows that in the CONGEST model, where vertices exchange O(log n)-bit messages with neighbors each round, the sparsest cut value φ of a weighted undirected graph can be approximated by a simple spectral algorithm: every vertex outputs φ̃ with φ ≤ φ̃ ≤ √(2.01 φ), in O(log² n/φ) rounds. This matches the general Cheeger bound up to a small constant, which is the best spectral methods can do. The previous fastest approach relied on expander decompositions and was slower or coarser in most regimes. The same eigenvalue-estimation machinery also gives k-way conductance to O(√φ_k), additive-epsilon estimates of the first k Laplacian eigenvalues, and an Ω(D) LOCAL lower bound showing the diameter term is necessary.","feed_headline":"Sparsest cut approximated within a √2.01 factor","feed_subtitle":"A simple spectral routine gives every node the conductance value in O(log²n/φ) rounds.","key_machinery":"The engine is the power method on M = 2I − L, run as local matrix-vector multiplications: each vertex holds one coordinate and sends it to neighbors, so one step costs one CONGEST round. The trick is to aim at the second-largest eigenvalue of M rather than the largest: subtract the component along √deg, the known eigenvector for eigenvalue 0 of L, and re-orthogonalize periodically. A bit-precision lemma keeps messages at O(log n) bits by truncating coordinates to their Θ(log n) most significant bits. Cheeger's Inequality and its higher-order analogue convert the resulting λ2 (or λ_k) estimates into sparsest cut (or k-way conductance) approximations.","core_discovery":"The central claim is that the normalized Laplacian's second-smallest eigenvalue λ2 can be approximated additively in O(log² n/ε + log n/ε²) CONGEST rounds using a distributed power method on M = 2I − L, with periodic subtraction of the known dominant eigenvector √deg to keep rounding errors from pulling the iteration toward eigenvalue 2. From λ2, Cheeger's Inequality gives the √2-factor sparsest-cut approximation; setting ε = Θ(φ) yields the O(log² n/φ)-round bound. The paper further claims the same approach extends to the k smallest eigenvalues, giving k-way conductance via the higher-order Cheeger inequality, and proves an Ω(D) lower bound in LOCAL for multiplicative λ2 approximation, show","pith_inferences":["The method is value-only; converting it to an output cut would require an additional step, likely by extracting the approximate eigenvector, which would make it directly usable as an expander-decomposition subroutine.","The same truncated power-method primitives could be used to estimate other graph invariants under CONGEST bandwidth constraints, such as PageRank-style linear systems or effective resistances.","The lower-bound construction combines paths, cliques, and stars; similar gadgets may yield Ω(D) lower bounds for other spectral quantities like λ_n or the spectral norm.","If the numerical-stability gap is resolved with an explicit bound on λ2, the approach could replace expander decompositions as the standard distributed sparsest-cut subroutine, since it is simpler and gives a stronger value approximation."],"forward_implications":["Sparsest cut approximation in CONGEST is brought within a log factor of the diameter lower bound for constant probability, and within O(log n) of it with high probability.","The √(2.01 φ) factor is essentially the Cheeger barrier; no purely spectral CONGEST algorithm can do better, so further improvements would need non-spectral techniques.","The k-way generalization gives the first distributed approximation of k-way conductance for constant k.","The eigenvalue estimates for λ1,...,λk and λn give cheap distributed tests for connectivity, bipartiteness-like behavior, and expansion without collecting the graph.","All upper bounds work in Broadcast CONGEST and weighted graphs, simplifying implementation compared with flow or expander-decomposition algorithms."],"supporting_citations":[{"why":"Supplies Cheeger's Inequality, which converts the λ2 estimate into a conductance approximation.","marker":"[AM85]"},{"why":"Supplies the higher-order Cheeger inequality, which converts λ_k estimates into k-way conductance bounds.","marker":"[LGT12]"},{"why":"Supplies the power method and its convergence guarantees, the core numerical primitive.","marker":"[GVL13]"},{"why":"Provides the previous best CONGEST sparsest-cut algorithm and baseline runtime and accuracy to compare against.","marker":"[CMGS25]"},{"why":"Prior distributed eigenvalue approximation reference that ignores message-size constraints; this paper's CONGEST implementation is contrasted with it.","marker":"[KM08]"},{"why":"Shows graphs with sparsest cut φ have diameter O(log n/φ), used to argue the upper bound is near-optimal.","marker":"[CGLP18]"},{"why":"Provides spectral graph theory basics and the cycle eigenvectors used in the lower bound constructions.","marker":"[Chu97]"}],"fun_headline_variants":["Sparsest cut in O(log²n/φ) rounds via eigenvalues","Distributed sparsest cut: √2 approximation from simple spectral method","Power method yields near-optimal sparsest cut in CONGEST","Eigenvalue estimation cracks sparsest cut faster","Simple spectral routine gives √2-approx sparsest cut in O(log²n/φ)"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is that, between periodic re-orthogonalizations, rounding error in the direction of the dominant eigenvector grows only polynomially; the proof's bound for this uses an inequality that is false when λ2 > 1, so the argument silently assumes λ2 is not too large (as it is, for instance, in complete graphs).","fun_headline_variants_meta":{"raw":{"variants":["Sparsest cut in O(log²n/φ) rounds via eigenvalues","Distributed sparsest cut: √2 approximation from simple spectral method","Power method yields near-optimal sparsest cut in CONGEST","Eigenvalue estimation cracks sparsest cut faster","Simple spectral routine gives √2-approx sparsest cut in O(log²n/φ)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000611,"raw_usage":{"total_tokens":2731,"prompt_tokens":849,"completion_tokens":1882,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":593,"completion_tokens_details":{"reasoning_tokens":1783}},"tokens_in":593,"tokens_out":1882,"duration_ms":16345,"temperature":1.0,"reasoning_tokens":1783,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T15:24:17.365652+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a complete graph K_n, where λ2 = n/(n−1) > 1, and run the CONGEST λ2-estimation algorithm with the stated rounding and periodic re-orthogonalization over l = Θ(log n/λ2) iterations. If the Rayleigh quotient drifts by more than n^{-Θ(1)} or stops tracking µ_{n-1}, the numerical-stability step is false and the claimed O(log² n/φ) bound collapses on that family.","supporting_citations":[],"review_version":1}