{"id":"1f35f482-1023-4d47-808f-eeb22ebcccdb","arxiv_id":"2505.14666","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives an O~(m^1.5 epsilon^-1) time algorithm for approximate spanning tree counting using recursive deletion of uncorrelated edge sets found via electrical-flow localization.","lead":"A new randomized algorithm estimates the number of spanning trees in a graph up to a multiplicative (1+epsilon) factor in time roughly m^1.5 / epsilon, where m is the number of edges. For sparse graphs this improves the previous best runtime, which was closer to n^1.875, by using electrical-flow localization to delete nearly independent edges.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Recursive deletion assumes G\\F remains connected; the determinant identity used in the recurrence only yields the spanning tree count for connected graphs, and the paper never proves an uncorrelated F cannot be a cut.","rationale":"The reader's weakest assumption is exactly the issue I consider most load-bearing: the algorithm's recursion requires G\\F to be connected, but the paper never proves it. This assumption is necessary for the central recurrence to compute the spanning tree count rather than some other determinant quantity. The concern is not an external disagreement with consensus; it is an internal gap in the proof of Theorem 1. I see no counterexample yet, but the missing argument is nontrivial because the uncorrelated condition involves weighted correlations and does not transparently rule out cuts. A concrete simulation or a cut-correlation lower bound would settle whether the gap is merely cosmetic or reflects a real failure mode. The reader's conditional verdict is appropriate: the algorithm is plausible but the proof is incomplete. Hence I leave the verdict unchanged.","tokens_in":11427,"tokens_out":38012,"duration_ms":346748,"concrete_test":"Simulate the exact correlation filtering (without sketching) on random graphs containing a two-edge cut whose edges have leverage <= 0.8 and edge weights chosen to make the mutual correlation <= rho; if both cut edges are ever returned, the recursion disconnects and the algorithm's output is invalid. Analytically, try to prove that for any cut C and any f in C with tau_f <= 0.8, Cor(f, C\\{f}) >= (w_f / w_max)^{1/2} |1 - tau_f|; if this lower bound exceeds rho, then no uncorrelated F can contain a cut, and the connectivity gap is a fixable missing lemma.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The algorithm's correctness rests on the identity in Section 3 and Lemma 5.2, which relate log T(G\\F) - log T(G) to sum_e log(1 - tau_e). Both are valid only when G\\F is connected, because for a disconnected graph T(G\\F) = 0 and det^+(L(G\\F)) is not n times the spanning tree count; log T is undefined. Figure 1 step 6 recurses on (V, E\\F, w) without checking or proving connectivity. The paper never establishes that a rho-uncorrelated set F (with all leverage scores <= 0.8 and rho <= 0.01) cannot contain all edges of a cut. This is not immediate from the definition: for a cut C, Cor(f, C\\{f}) can be as small as (w_f/w_max)^{1/2} |1 - tau_f| when weights are asymmetric, so a cut could pass the rho-threshold and be output by GetUncorrelated. If that happens, the recursive call computes det^+(L(G\\F)) rather than T(G\\F), and the recurrence no longer approximates the spanning tree count. This is the central missing invariant of the proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an algorithm ApproxSpanningTree that approximates the spanning tree weight of an undirected weighted graph by repeatedly deleting sets of \"uncorrelated\" edges. For a graph with m edges, n vertices, and polynomially bounded weights, it claims a (1+epsilon) multiplicative approximation in O~(m^{1.5} epsilon^{-1}) time, improving on the previous O~(m + n^{1.875} epsilon^{-7/4}) bound for sparse graphs. The main technical machinery is a determinant identity relating log T(G\\F) - log T(G) to a log-determinant of an |F|-by-|F| matrix whose off-diagonal entries are small for uncorrelated edge sets; such sets are found using the electrical flow localization theorem of Schild-Rao-Srivastava and standard leverage-score estimation. The paper gives detailed lemmas for estimating leverage scores, estimating weighted sums of leverage scores, and finding uncorrelated edge subsets, followed by a recursive algorithm and a phase-based variance analysis.","tokens_in":11674,"tokens_out":26746,"duration_ms":324048,"significance":"If correct, this is a notable improvement for sparse graphs and introduces a genuinely different approach to Laplacian determinant estimation. The proof is largely self-contained and builds on standard external tools (Laplacian solvers, leverage-score sketching, and l1-stable sketches), and the central claim is not circular: each estimator is derived from first principles, not from the theorem being proved. The main weaknesses are an unstated connectivity invariant for the recursive deletion step and a parameter regime (very small epsilon) that is not covered as written; both appear repairable, but they are load-bearing for the proof as presented.","major_comments":[{"comment":"The recurrence uses log T(G\\F), which is only defined when G\\F is connected, but the manuscript never states or proves that the deleted edge set F cannot disconnect G. This is load-bearing: if F contained all edges of a cut, the determinant identity of Section 3 would give det^+(L(G\\F)) = 0, so log T(G\\F) would be undefined and the recurrence would not approximate the spanning tree count. The gap is repairable: under the hypotheses of Lemma 5.2, the matrix A with entries A_{e,f} = w_e^{1/2} b(e)^T L(G)^† b(f) w_f^{1/2} has diagonal entries at most 0.88 and off-diagonal row sums at most rho <= 0.01, so ||A||_2 <= 0.89, det(I-A) > 0, and hence det^+(L(G\\F)) > 0; for a Laplacian this positivity is equivalent to G\\F being connected. Please insert this invariant explicitly before Lemma 5.2 and use it inductively in the proof of Theorem 1.","section":"§5, Figure 1 / Lemma 5.2"},{"comment":"The theorem is stated for all 0 < epsilon < 1, but the algorithm in Figure 1 has no base case and calls GetUncorrelated with k = Theta(epsilon sqrt(m) / (log m)^3). For epsilon smaller than about (log m)^3 / sqrt(m), this k is less than 1, so Lemma 4.3 cannot be applied as stated. Additionally, Lemma 5.1 can reduce a connected graph to an empty graph, and the recursion needs a stopping rule. These issues are local but must be fixed for the theorem to hold in the stated range, for example by using exact determinant computation when epsilon is below a threshold (noting that the runtime is then within the claimed bound) or by defining k = max(1, Theta(epsilon sqrt(m)/(log m)^3)) and rederiving the error bound in the k = 1 regime.","section":"§5, Theorem 1"}],"minor_comments":[{"comment":"In the proof, after two Markov inequalities the algorithm keeps at least 1.8k edges, not 1.9k (at most 0.1|F+| = 0.2k edges are discarded); the conclusion is unaffected because 1.8k >= k, but the number should be corrected.","section":"§4.3, Lemma 4.3"},{"comment":"The displayed chain ending in \"= 2|F|rho^2\" should be \"<= 2|F|rho^2\", and the proof uses theta_e <= 1 to drop the theta_e theta_f factors; please state explicitly that the lemma requires theta in [0,1]^F.","section":"§4.2, Lemma 4.2"},{"comment":"The lemma is stated as succeeding with high probability, but the proof only establishes a constant probability that at least k edges survive; please add the standard repetition argument (O(log n) independent trials) that upgrades the success probability.","section":"§4.3, Lemma 4.3"},{"comment":"The recursion has no stated base case: when Lemma 5.1 reduces the graph to an empty graph or to a graph with no edges, steps 2-5 are undefined. Specify a stopping rule, e.g., compute the determinant exactly when m is below a constant.","section":"§5, Figure 1"},{"comment":"The phase analysis states that variance is additive over iterations; this is correct because each recursive call uses fresh randomness, but the proof should present the conditional-expectation argument: E[X_i | history] telescopes to the total log-ratio, while the conditional variances add.","section":"§5, proof of Theorem 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is close to correct, but the written proof omits an invariant that is needed for the recurrence to be well-defined, and the very-small-epsilon regime is not handled. Both issues seem fixable without changing the main algorithmic idea, so I recommend major revision rather than rejection. The authors should also patch the base case and a few small arithmetic statements before the paper is publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper deserves a serious referee, and I expect a conditional accept after a small revision. The core result is real: an O~(m^1.5 eps^{-1}) algorithm for (1+eps)-approximating the spanning tree count, beating the previous O~(m + n^1.875) for sparse graphs. The approach is genuinely different from the Schur-complement/determinantal-sparsification line: it repeatedly finds a small 'uncorrelated' edge set via electrical flow localization, deletes it, and recurses. That's a nice idea and the high-level structure is sound.\n\nThe main gap is exactly what the stress-test flags: the recursion assumes G\\F remains connected, and the paper never says why. The determinant identity in Section 3 and Lemma 5.2 require a connected graph; for a disconnected G\\F, T(G\\F)=0 and the logarithm breaks. That said, the missing invariant is true and short to prove. For a cut C, sum_{e in C} tau_e = 1, and for any two cut edges e,f, |M_{e,f}| = sqrt(tau_e tau_f). If F is rho-uncorrelated with rho<0.4 and every tau_e <=0.8, then taking the edge f* with maximum tau (0.8) gives Cor(f*, C\\{f*}) >= sqrt(0.8)*sqrt(0.2) = 0.4, a contradiction. So no such F can contain a cut. The authors just need to add this lemma. It is a gap in exposition, not a hole in the result.\n\nOther issues are minor. Lemma 4.3 says 'at least 1.9k edges are kept' but the previous line gives at most 0.1|F+| = 0.2k discarded, so 1.8k. Just a typo. The pseudocode in Figure 1 has no base case; the text should say what happens when m is small. The phase-level variance bound is compressed but the calculation checks out: per-iteration bias/variance O(k_i^3/m_i^2 log^4), times m_i/k_i iterations gives O(eps^2/log^2) per phase, summing to O(eps^2).\n\nThe literature use is fair; the self-citations are to background tools, not to the central claim. The proof is not circular.\n\nBottom line: read it as a solid FOCS/SODA-style paper that needs a small revision. The connectivity lemma is the one thing a referee must insist on; everything else is cosmetic. Send it to peer review.","headline":"A real runtime improvement and a genuinely new algorithmic idea, with a missing connectivity argument that is fixable and likely true.","tokens_in":12176,"tokens_out":16845,"would_cite":true,"duration_ms":151882,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":null,"created_at":"2026-08-07T15:31:48.256113+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":null,"supporting_citations":[],"review_version":1}