{"id":"29c6ab9f-62a2-4dce-ad79-b32e262f6cec","arxiv_id":"2411.13334","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new algorithm samples a nearly uniform spanning tree of an n-vertex graph in about n^0.657 rounds of the Congested Clique model, the first sublinear-time result for this problem.","lead":"Spanning trees are the skeleton of any graph, and this paper shows how to sample one nearly uniformly many times faster than before in a distributed model where every machine talks to every other. It is the first sublinear-time algorithm for this task in the Congested Clique model, and it introduces a new top-down technique for building long random walks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 7's error recurrence is unsound: from E(k) ≤ (n+1)E(k/2)+δ the solution is δ(n+1)^{log k}, not δ k^c log k, so the inverse-poly precision claim for Schur/shortcut computation is unproven and likely needs a different parameter regime.","rationale":"The reader identified the computation of Schur and shortcut transition matrices (Corollaries 2 and 3) as the least secure part of the paper. My stress-test agrees and locates a specific technical flaw: Lemma 7's error recurrence is not solved correctly. From E(k) ≤ (n+1)E(k/2)+δ, the solution is δ(n+1)^{log k}, which for k up to n^3 is super-polynomial in n, contradicting the claimed O(δ k^c log k) bound. This means the paper's explicit precision budget (β = 1/poly(n) with entries in O(log n) bits) is not established. The asymptotic round count would likely survive a fix that allows O(log^2 n)-bit entries, but the proof as written is invalid. Since Theorem 1 relies on per-phase Schur/shortcut computation, the central claim is supported by an unproven numerical primitive. I therefore recommend conditional acceptance: the authors should correct Lemma 7's error analysis and confirm Corollaries 2 and 3 with the revised precision parameters. I agree fully with the reader's weakest-assumption identification, and the concrete test above would settle whether the flaw is merely a proof gap or a substantive obstruction.","tokens_in":30999,"tokens_out":43939,"duration_ms":480551,"concrete_test":"Re-derive Lemma 7 tracking E(k) as maximum entrywise subtractive error, including the E^2 term in the squaring step, and solve the recurrence exactly for k = n^3. Then run the paper's iterative rounding scheme on a concrete transition matrix with column sums Ω(n) that persist across powers (e.g., an undirected lollipop graph) with δ = β/(k^c log k), β = n^{-5}, c = 1, and compare the actual max error of M^k to β. If the error exceeds β, Lemma 7's parameter choice fails and Corollaries 2 and 3 require a corrected precision analysis.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 7 claims that for any transition matrix M and k = O(n^{c1}), M^k can be computed with subtractive error β = Ω(1/n^{c2}) in Õ(n^α) rounds, deriving E(k) ≤ (n+1)E(k/2)+δ and concluding E(k)=O(δ k^c log k). This inference is incorrect: solving the recurrence gives E(k)=O(δ (n+1)^{log k}) = O(δ k^{log(n+1)}). For k = n^3 this is δ n^{3 log(n+1)}, super-polynomial in n, not δ n^{O(1)}. Consequently the proof's choice δ = Θ(β/(k^c log k)) does not achieve final inverse-polynomial error β. Corollaries 2 and 3 rely directly on Lemma 7 to compute the ShortCut and Schur-complement transition matrices with inverse-polynomial subtractive error in Õ(n^α) rounds; with the corrected amplification, the intermediate precision log(1/δ) must be Θ(log^2 n) bits rather than Θ(log n) bits. The extra poly-log factor is absorbed by Õ, so the asymptotic round bound may survive, but the paper's explicit parameter choices and the TV-error analysis in Lemma 9, which assumes every matrix entry fits in O(log n) bits, are not justified as written. Since the phase-cost argument for Theorem 1 rests on these corollaries, the central claim is currently supported by an invalid numerical-precision proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents the first sublinear-round algorithm in the CongestedClique model for approximately sampling a uniform spanning tree. The main algorithm, described in Section 2, uses a top-down walk-filling method in which a long target walk is generated phase by phase, truncating each phase after roughly sqrt(n) distinct vertices are visited, and then resampling the locations of midpoints via weighted perfect matchings. Later phases work on Schur complement and shortcut graphs to avoid previously visited vertices. The claimed running time is O~(n^{1/2+alpha}) rounds for total variation error 1/n^c, where alpha is the matrix-multiplication exponent. A second contribution (Section 3) is a load-balanced doubling algorithm that takes random walks of length O(tau) in roughly tau/n polylog rounds, yielding O(log^3 n)-round spanning-tree sampling for graphs with O(n log n) cover time. The paper also sketches an exact-sampling variant with O~(n^{2/3+alpha}) rounds.","tokens_in":31186,"tokens_out":27388,"duration_ms":296432,"significance":"If the proofs are completed, the main result is a significant advance: no prior sublinear-round distributed algorithm for uniform spanning tree sampling in the CongestedClique model is known, and the top-down approach with Schur-complement shortcutting and perfect-matching-based resampling is a genuinely novel algorithmic contribution. The secondary doubling result is also useful and appears to give the first polylogarithmic-round algorithm for long random walks in this model. The paper gives credit appropriately to prior sequential and distributed work, and the high-level correctness argument for the sequential and matching-sampling parts (Lemmas 1-4) is convincing. However, the numerical-precision infrastructure that supports the main theorem contains a concrete error (Lemma 7), and there are additional missing justifications in the high-probability and precision analysis. These are load-bearing, so the paper is not ready for acceptance in its current form.","major_comments":[{"comment":"The recurrence analysis in Lemma 7 is incorrect. From E(1) <= delta and E(k) <= (n+1)E(k/2)+delta, the solution is E(k) <= delta (n+1)^{log2 k}, not O(delta k^c log k). Since k = O(n^{c1}), the corrected bound is delta n^{c1 log2(n+1)}, which is super-polynomial in n. Consequently, the choice delta = Theta(beta/(k^c log k)) does not give the claimed inverse-polynomial final error beta. Corollaries 2 and 3 use Lemma 7 to compute the Schur and shortcut transition matrices with inverse-polynomial subtractive error in O~(n^alpha) rounds, and Lemma 9 relies on those matrices having such error, so the proof of Theorem 1 is currently unsupported at this point. The claim is plausibly repairable by choosing delta = beta (n+1)^{-log2 k}, which requires O(log^2 n) bits per entry and is absorbed by the O~ notation, but the proof as written and the statement in Section 2.5 that entries fit in O(log n)-bit words must be revised.","section":"Section 2.4, Lemma 7"},{"comment":"The claim 'Using the fact that the cover time ... is O(n^3) and Markov's inequality, we see that an O(n^3) length random walk covers the graph with probability at least 1/2. Thus, T = O~(n^3) with high probability' is not justified. Markov's inequality gives P(cover time > c n^3) <= 1/c, so a constant multiple of the expected cover time does not yield failure probability epsilon/(2 sqrt(n)); an exponential tail bound or a different argument is needed. The choice of ell = n^3 log(4 sqrt(n)/epsilon) and the phase-failure accounting in Lemma 6 depend on this high-probability statement. This is repairable by proving or citing an exponential tail for the cover time, or by union-bounding per-vertex hitting times, but as written the argument is incomplete.","section":"Section 2.1 and Lemma 6"},{"comment":"The proof of Lemma 9 assumes that every midpoint pair (a,c) satisfies P^2[a,c] > 1/n^{k1} and asserts that the 'second term' in the displayed union bound bounds the failure of this assumption, but no argument is given for the existence of a single k1 that works for all sampled midpoint pairs. The issue is load-bearing because Lemma 8's total-variation bound is 2 beta n^{c+1}/W^2[p,q], which is meaningless if W^2[p,q] can be super-polynomially small. In addition, the union bound in Lemma 9 counts only O~(n^3) midpoints, whereas the full algorithm runs O(sqrt(n)) phases and therefore chooses O~(n^{3.5}) midpoints overall; the bound can absorb this, but the accounting should be corrected. The lower-bound assumption and the union bound need a separate, explicit proof.","section":"Section 2.5, Lemma 9"},{"comment":"The load-balanced doubling step is underspecified in a way that affects correctness. In Step 2, every prefix walk whose endpoint is v and whose first-half index is i is routed to h_s(v, k-i+1); in Step 3, the unique suffix from v with the complementary index k-i+1 is routed to the same key. If two different prefix walks end at v with the same index i, both arrive at the same machine, but only one suffix is available for concatenation. The algorithm says 'each machine w receiving two walks' but does not say what to do when more than two arrive or when multiple prefixes must share one suffix, and Lemma 10 bounds only total load, not this multiplicity. Relatedly, Fact 1 is applied to indicators Y_j whose underlying hash keys are not necessarily distinct, so the t-wise-independence hypothesis is not met as stated. The correctness of the merging step requires a resolution of this multiplicity, not just a load-balancing argument.","section":"Section 3, Steps 2-4"}],"minor_comments":[{"comment":"The word 'accuraracy' should be 'accuracy' in the first sentence of Section 2.4.","section":"Section 2.4"},{"comment":"The coupling argument says 'sample y from C', but C = U - U-hat can have negative entries and is not a probability distribution. The intended bound is the standard one: the normalized approximate distribution has total-variation distance at most 1 - Z/W^2[p,q] <= 2 beta n / W^2[p,q]; this should be stated directly.","section":"Section 2.5, Lemma 8"},{"comment":"The phrase 'all the vertices in R are absorbing' is imprecise: only the R-copy vertices are absorbing, while the L-copy vertices are transient. The intended meaning is clear, but the wording should be corrected to avoid confusion.","section":"Section 2.4, Corollary 2"}],"recommendation":"major_revision","confidential_remarks":"The first reader's positive assessment is understandable: the main algorithmic architecture is novel and the high-level correctness story is plausible. However, the numerical-precision section contains a concrete mathematical error (Lemma 7) that is load-bearing for the main theorem, and Section 3's doubling proof has an unresolved multiplicity issue. Both problems appear fixable within the scope of the paper, so I recommend major revision rather than rejection. I have no concerns about attribution or fit with the journal's scope; the related-work discussion is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is the first sublinear-round algorithm for sampling a uniform spanning tree in the Congested Clique, and the main ideas are genuinely new. But the numerical-precision section has a real error in Lemma 7 that needs fixing before the proof is trustworthy.\n\nWhat's new and good: the top-down walk filling approach is a real departure from the usual bottom-up doubling, and the use of Schur complement and shortcut graphs to skip visited vertices is elegant. The distributed truncation via binary search and the compression of midpoints via weighted perfect matching sampling are clever and, as far as I can tell, correctly argued. Lemma 3 relating the midpoint ordering to perfect matchings works. The high-level structure is sound: O(sqrt(n)) phases, each costing about a matrix multiplication, giving O-tilde(n^{1/2+alpha}) rounds. The load-balanced doubling result for short walks is a solid bonus.\n\nThe soft spot: Lemma 7's error analysis is wrong. The recurrence E(k) <= (n+1)E(k/2)+delta does not solve to O(delta k^c log k); it solves to O(delta (n+1)^{log k}), which for k = n^3 is super-polynomial. So the paper's choice of delta does not deliver inverse-polynomial error as claimed. That means Corollaries 2 and 3, which rely on Lemma 7 to compute the Schur and shortcut graphs, don't have the promised guarantee as written. The stress-test note is right about this. That said, this looks fixable: choose delta to absorb the (n+1)^{log k} factor, which costs O(log^2 n) bits per entry; the round count still lands in O-tilde(n^alpha), and Lemma 9's union bound can likely be adjusted. So the main theorem probably survives, but the proof needs real work.\n\nMinor: the exact-sampling appendix is only a sketch, and Lemma 9 is lighter on detail than the rest. No circularity red flags; the 'first sublinear' claim checks out against the cited literature.\n\nWho for: anyone working on distributed graph algorithms, especially sampling in Congested Clique or MPC. It's worth a serious referee, but I'd want a careful review of the precision section before acceptance.","headline":"First sublinear-round spanning tree sampler for Congested Clique with genuinely new techniques, but the numerical-precision proof has a genuine gap that likely can be patched.","tokens_in":31864,"tokens_out":8766,"would_cite":true,"duration_ms":83954,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","05C85","05C81"],"pacs":[],"model":"deepseek-v4-flash","headline":"Sampling a uniform spanning tree now takes sublinear rounds in the congested clique","keywords":["uniform spanning tree","random spanning tree","Congested Clique","distributed graph algorithm","random walk","Schur complement","matrix multiplication","weighted perfect matching"],"falsifier":"Take a concrete graph, such as a barbell or an expander, and compare the row-renormalized $O(n^3 \\log(1/\\delta))$-step absorbing-walk approximation of the shortcut and Schur-complement transition matrices to the exact first-visit distribution; if the total-variation error after renormalization exceeds $O(1/n^c)$, or if the computation requires more than $\\widetilde{O}(n^\\alpha)$ rounds, the per-phase account of the theorem fails.","tokens_in":30621,"feed_emoji":"🌲","tokens_out":10608,"duration_ms":95428,"temperature":0.7,"pith_summary":"The paper establishes that uniform spanning tree sampling can be done in sublinear time in the CongestedClique distributed model: $\\widetilde{O}(n^{1/2+\\alpha})$ rounds, about $n^{0.657}$ with the current matrix-multiplication exponent, for arbitrary unweighted graphs and inverse-polynomial total-variation error. The algorithm works top-down: it samples the endpoint of a very long walk, then fills in midpoints level by level, truncating each phase once $\\sqrt{n}$ new vertices are visited. Already-visited vertices are skipped by working on Schur-complement and shortcut graphs, and the midpoints reach the coordinating machine as a compressed multiset whose positions are recovered by sampling a weighted perfect matching. If the paper is right, random spanning tree sampling loses its status as an inherently linear-time distributed task, and the per-phase matrix-multiplication cost is the remaining barrier.","feed_headline":"Sampling a uniform spanning tree takes sublinear rounds","feed_subtitle":"A top-down walk-filling algorithm skips visited vertices and samples matchings to beat the n-round barrier","key_machinery":"Three objects carry the algorithm. The first is the top-down walk-filling recursion: instead of stitching short walks bottom-up, it samples the endpoint of a length-$\\widetilde{\\Theta}(n^3)$ walk from a power of the transition matrix and recursively samples midpoints from the Bayes-rule distribution $P^{\\ell/2}[s,v]\\,P^{\\ell/2}[v,e]$. The second is the Schur complement graph of the still-unvisited set $S$, whose random walk matches the original walk with previously visited vertices removed, together with the shortcut graph that recovers first-visit edges in the original graph; both are approximated in $\\widetilde{O}(n^\\alpha)$ rounds using matrix multiplication. The third is the compressed midpoint-placement step: machines send only the multiset of midpoints, and the coordinating machine resamples their positions by drawing a weighted perfect matching in a complete bipartite graph whose edge weights are products of transition probabilities. This reduction to weighted perfect matching is what keeps communication inside the CongestedClique bandwidth.","core_discovery":"The paper's central claim is that an approximately uniform spanning tree of an arbitrary unweighted $n$-vertex graph can be sampled in the CongestedClique model in $\\widetilde{O}(n^{1/2+\\alpha})$ rounds, where $O(n^\\alpha)$ is the model's matrix-multiplication time (currently $\\alpha \\approx 0.157$), matching the uniform distribution within total variation distance $\\varepsilon = \\Omega(1/n^c)$ for any fixed $c>0$. This is the first $o(n)$-round algorithm for the problem. The construction implements the classical first-visit-edge characterization of uniform spanning trees by simulating a covering-length random walk through $O(\\sqrt{n})$ phases, each responsible for $O(\\sqrt{n})$ newly visited vertices. Each phase runs in roughly matrix-multiplication time: matrix powers drive midpoint sampling, Schur-complement and shortcut graphs skip previously visited vertices while preserving the original walk's distribution, and a compressed communication step reduces midpoint placement to sampling a weighted perfect matching. An exact-sampling variant runs in $\\widetilde{O}(n^{2/3+\\alpha})$ rounds, still sublinear. A separate load-balanced doubling algorithm samples shorter walks and gives $O(\\log^3 n)$-round spanning tree sampling for graphs with $O(n \\log n)$ cover time.","pith_inferences":["A testable extension the paper leaves implicit is transferring the perfect-matching compression to other all-to-all distributed models; the same bottleneck that blocks bottom-up doubling there is exactly what the compression addresses.","If the per-phase Schur and shortcut matrices could be produced by a distributed Laplacian solver instead of matrix multiplication, the authors' own barrier discussion suggests the exponent could approach $1/2$; this is an editorial next step, not a claim of the paper.","A known bound says a length-$n$ walk in an unweighted graph visits many distinct vertices; if an analogous bound held for weighted Schur-complement graphs, a simpler phase organization might become viable, though the paper notes this would not beat its current exponent."],"forward_implications":["If the main theorem holds, uniform spanning tree sampling becomes a sublinear-round problem in the CongestedClique for every fixed inverse-polynomial accuracy target, alongside other fundamental graph tasks.","The exact-sampling variant, at $\\widetilde{O}(n^{2/3+\\alpha})$ rounds, shows the sublinear result is not an artifact of approximation error.","For graphs with cover time $O(n \\log n)$, the load-balanced doubling algorithm samples spanning trees in $O(\\log^3 n)$ rounds, making near-instant distributed sampling possible on expanders and dense random graphs.","Because each phase is dominated by matrix multiplication, any future improvement to CongestedClique matrix multiplication immediately improves the main exponent $n^{1/2+\\alpha}$.","The weighted-perfect-matching compression gives a general template for distributing recursive random-walk generation when the walk is too long to ship to a single machine."],"supporting_citations":[{"why":"Supplies the random-walk characterization that first-visit edges form a uniform spanning tree, the distribution the algorithm targets.","marker":"[1]"},{"why":"Independent statement of the same first-visit-edge characterization, used as the basis for the whole sampling scheme.","marker":"[12]"},{"why":"Provides the O(n^alpha)-round CongestedClique matrix multiplication used for matrix powers, Schur complements, and shortcut matrices.","marker":"[17]"},{"why":"Provides the FPRAS for the permanent used by the coordinating machine to approximately sample weighted perfect matchings.","marker":"[46]"},{"why":"Shows how to convert approximate counting into approximate sampling, yielding the polynomial-time sampler for weighted perfect matchings.","marker":"[47]"},{"why":"Introduces the shortcutting idea for faster random spanning tree generation, adapted here to recover first-visit edges after skipping visited vertices.","marker":"[52]"},{"why":"Supplies the Schur complement definition and the fact that Schur complements of Laplacians are graph Laplacians, which underlies the derivative graphs.","marker":"[55]"},{"why":"Supplies the constant-round routing protocol that lets every machine exchange O(n) messages, the bandwidth assumption behind each phase's communication bound.","marker":"[56]"},{"why":"Provides the sequential almost-linear-time sampler and the theorem that random walks on Schur complement graphs match original walks restricted to the unvisited set.","marker":"[69]"}],"fun_headline_variants":["Sublinear rounds for uniform spanning tree sampling in Congested Clique","Beat n-round barrier: sample uniform spanning tree in n^0.657 rounds","First sublinear-time algorithm for sampling uniform spanning trees","Top-down walk filling: sample uniform spanning trees in sublinear rounds","Shortcut random walks with Schur complements for sublinear spanning tree sampling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the shortcut and Schur-complement transition matrices for any subset of vertices can be computed in $\\widetilde{O}(n^\\alpha)$ rounds with inverse-polynomial subtractive error, using a finite power $k = O(n^3 \\log(1/\\delta))$ of an absorbing-walk matrix followed by row renormalization; if that computation is not both fast and accurate enough in every phase, the claimed $\\widetilde{O}(n^{1/2+\\alpha})$ total collapses.","fun_headline_variants_meta":{"raw":{"variants":["Sublinear rounds for uniform spanning tree sampling in Congested Clique","Beat n-round barrier: sample uniform spanning tree in n^0.657 rounds","First sublinear-time algorithm for sampling uniform spanning trees","Top-down walk filling: sample uniform spanning trees in sublinear rounds","Shortcut random walks with Schur complements for sublinear spanning tree sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000816,"raw_usage":{"total_tokens":3702,"prompt_tokens":1202,"completion_tokens":2500,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":818,"completion_tokens_details":{"reasoning_tokens":2408}},"tokens_in":818,"tokens_out":2500,"duration_ms":16312,"temperature":1.0,"reasoning_tokens":2408,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:34:04.725812+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a concrete graph, such as a barbell or an expander, and compare the row-renormalized $O(n^3 \\log(1/\\delta))$-step absorbing-walk approximation of the shortcut and Schur-complement transition matrices to the exact first-visit distribution; if the total-variation error after renormalization exceeds $O(1/n^c)$, or if the computation requires more than $\\widetilde{O}(n^\\alpha)$ rounds, the per-phase account of the theorem fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the random-walk characterization that first-visit edges form a uniform spanning tree, the distribution the algorithm targets."},{"cited_title":"Generating random spanning trees","cited_arxiv_id":null,"evidence_quote":"Independent statement of the same first-visit-edge characterization, used as the basis for the whole sampling scheme."},{"cited_title":"Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela","cited_arxiv_id":null,"evidence_quote":"Provides the O(n^alpha)-round CongestedClique matrix multiplication used for matrix powers, Schur complements, and shortcut matrices."},{"cited_title":"A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.J","cited_arxiv_id":null,"evidence_quote":"Provides the FPRAS for the permanent used by the coordinating machine to approximately sample weighted perfect matchings."},{"cited_title":"Valiant, and Vijay V","cited_arxiv_id":null,"evidence_quote":"Shows how to convert approximate counting into approximate sampling, yielding the polynomial-time sampler for weighted perfect matchings."},{"cited_title":"Kelner and Aleksander Madry","cited_arxiv_id":null,"evidence_quote":"Introduces the shortcutting idea for faster random spanning tree generation, adapted here to recover first-visit edges after skipping visited vertices."},{"cited_title":"Approximate Gaussian Elimination","cited_arxiv_id":null,"evidence_quote":"Supplies the Schur complement definition and the fact that Schur complements of Laplacians are graph Laplacians, which underlies the derivative graphs."},{"cited_title":"Optimal deterministic routing and sorting on the congested clique","cited_arxiv_id":null,"evidence_quote":"Supplies the constant-round routing protocol that lets every machine exchange O(n) messages, the bandwidth assumption behind each phase's communication bound."},{"cited_title":"An almost-linear time algorithm for uniform random spanning tree generation","cited_arxiv_id":null,"evidence_quote":"Provides the sequential almost-linear-time sampler and the theorem that random walks on Schur complement graphs match original walks restricted to the unvisited set."}],"review_version":1}