Pith. sign in

REVIEW 4 major objections 3 minor 77 references

Sublinear-Time Sampling of Spanning Trees in the Congested Clique

T0 review · 4 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Sampling a uniform spanning tree now takes sublinear rounds in the congested clique

desk verdict 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. read the letter →

arxiv 2411.13334 v2 pith:35XU5JBF submitted 2024-11-20 cs.DC

Sriram V. Pemmaraju , Sourya Roy , Joshua Z. Sobel This is my paper · ORCID
classification cs.DC MSC 68W1505C8505C81
keywords uniformspanningtreerandomCongestedCliquedistributedgraphalgorithmwalkSchurcomplementmatrixmultiplicationweightedperfectmatching
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

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.

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 (4)
  1. [Section 2.4, Lemma 7] 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.
  2. [Section 2.1 and Lemma 6] 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.
  3. [Section 2.5, Lemma 9] 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.
  4. [Section 3, Steps 2-4] 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.
minor comments (3)
  1. [Section 2.4] The word 'accuraracy' should be 'accuracy' in the first sentence of Section 2.4.
  2. [Section 2.5, Lemma 8] 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.
  3. [Section 2.4, Corollary 2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found: Theorem 1 follows from external Aldous-Broder, cover-time bounds, Schur/shortcut graph theory, and the permanent FPRAS; the paper's self-citations are contextual only.

full rationale

The derivation chain is self-contained with respect to external results. Theorem 1 is built on the Aldous-Broder first-visit edge sampling theorem [1,12], the O(n^3) cover-time bound, the Schur complement and shortcut graph framework from [52,55,69], and the permanent FPRAS of Jerrum-Sinclair-Vigoda [46] combined with the sampling-to-counting reduction [47]; none of these are redefined inside the paper. The internal lemmas are reductions: Lemma 3 reduces midpoint placement to weighted perfect matching, Lemma 4 bounds the matching-sampling error, and Lemma 8 reduces entrywise subtractive error to total variation error. These reductions do not equate a predicted quantity with a fitted input, and no parameter is fitted to a subset of the output distribution. The only self-citations ([45], [67], [68]) appear in related-work surveys and are not load-bearing; no uniqueness theorem or ansatz is imported from the authors' prior work. The most fragile step, Lemma 7's multiplicative error recurrence and the resulting precision claim for Corollaries 2 and 3, appears mathematically questionable, but an unsound bound is a correctness defect, not a circular reduction: the claimed computation of M^k is not defined in terms of the spanning-tree output it supports, and no equation equates the prediction with the input. Therefore the central contribution does not reduce to its own claims by construction.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The core results rest on classical theorems (Aldous-Broder, cover time bounds, Schur complement properties, permanent sampling) and on model primitives (Congested Clique matrix multiplication and Lenzen routing). The algorithmic choices of target walk length and phase vertex budget are explicit tuning parameters, not fitted to data. No new entities are postulated.

free parameters (2)
  • Target walk length per phase ℓ = smallest power of two ≥ log(4√n/ε) n^3
    Chosen to ensure a length-ℓ random walk visits at least √n distinct vertices with high probability in each phase; it is an algorithmic parameter, not fitted to any observed data.
  • Phase vertex budget ρ = ⌊√n⌋
    Chosen so that a phase visits Θ(√n) distinct vertices, balancing the number of phases (O(√n)) against the bandwidth needed for midpoint compression; set by the algorithm design, not by fitting.
assumptions (7)
  • standard math Markov property of random walks
    Used in Lemma 1 to prove the sequential top-down sampler and in Lemma 3 for the independence of midpoint choices at each level.
  • standard math Cover time of an n-vertex unweighted undirected graph is O(n^3)
    Used to set the per-phase walk length ℓ = Θ(n^3 poly log n) so that each phase visits Θ(√n) distinct vertices with high probability (Section 2.1).
  • standard math Schur complement of a Laplacian is a Laplacian and the restricted walk identity
    Establishes that a walk on Schur(G,S) has the same distribution as a walk on G restricted to S, used in Section 2.2 for subsequent phases.
  • standard math Jerrum-Sinclair-Vigoda FPRAS for the permanent and Jerrum-Valiant-Vazirani sampling-to-counting reduction
    Used by the leader to sample weighted perfect matchings in polynomial time (Section 1.8 and Section 2.1.3).
  • standard math Matrix multiplication in Congested Clique costs O(n^α) rounds (Censor-Hillel et al.)
    Powers of transition matrices and the Schur/shortcut graphs are computed using this primitive; it sets the per-phase exponent α.
  • ad hoc to paper For every midpoint sampled, the two-step transition probability W^2[p,q] exceeds 1/n^{k1} for a suitably large constant k1
    Assumed in Lemma 9 to bound the error from approximate matrix entries; the paper argues the opposite event has probability at most Õ(n^3/n^{k1}) over all midpoints, and chooses k1 large enough to make it negligible. This is a paper-specific technical condition, not a general graph axiom.
  • domain assumption Lenzen's routing lemma allows every machine to send and receive O(n) messages in O(1) rounds
    Used throughout to argue that the communication needed for midpoint requests, counts, and matrix entries fits in the Congested Clique model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sublinear-Time Sampling of Spanning Trees in the Congested Clique." pith.science (2026). https://pith.science/paper/35XU5JBF

@misc{pith2026241113334,
  author       = {Pith},
  title        = {Pith review of: Sublinear-Time Sampling of Spanning Trees in the Congested Clique},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/35XU5JBF}},
  note         = {Machine review of arXiv:2411.13334}
}
abstract

We present the first sublinear-in-$n$ round algorithm for sampling an approximately uniform spanning tree of an $n$-vertex graph in the CongestedClique model of distributed computing. In particular, our algorithm requires $\Tilde{O}(n^{0.657})$ rounds for sampling a spanning tree within total variation distance $1/n^c$, for arbitrary constant $c > 0$, from the uniform distribution. More precisely, our algorithm requires $\Tilde{O}(n^{1/2 + \alpha})$ rounds, where $O(n^\alpha)$ is the running time of matrix multiplication in the CongestedClique model (currently $\alpha = 1 - 2/\omega = 0.157$, where $\omega$ is the sequential matrix multiplication time exponent). We can adapt our algorithm to give exact rather than approximate samples, but with a larger, though still $o(n)$, runtime of $\Tilde{O}(n^{2/3+\alpha}) = O(n^{.824})$. In a remarkable result, Aldous (SIDM 1990) and Broder (FOCS 1989) showed that the first visit edge to each vertex, excluding the start vertex, during a random walk forms a uniformly chosen spanning tree of the underlying graph. Our algorithm is a significant departure from known techniques, featuring a top-down walk filling approach paired with Schur complement graphs for walk shortcutting. To make this idea work in the CongestedClique model, we present a novel compressed random walk reconstruction algorithm, based on randomly sampling a weighted perfect matching. In addition, we show how to take somewhat shorter random walks even more efficiently in the CongestedClique model, obtaining an $O(\log^3 n)$-round algorithm for uniformly sampling spanning trees from graphs with $O(n\log n)$ cover times. These results are obtained by adding a load balancing component to the random walk algorithm of Bahmani, Chakrabarti and Xin (SIGMOD 2011) that uses the bottom-up ``doubling'' technique.

Figures

Figures reproduced from arXiv: 2411.13334 by the authors.

Figure 1
Figure 1. This figure illustrates how machine M adds midpoints to the walk Wi to obtain Wi+1. Note that in Wi there exist the distinct start-end pairs: (1, 3),(3, 2),(2, 1),(1, 2). M sends the count cp,q of each start-end pair (p, q) to the machine Mp,q responsible for that pair. The machine Mp,q then generates a sequence Πp,q containing cp,q midpoints. For example, machine M1,3 generates Π1,3 = (4, 2) indicating that midpoin… view at source ↗
Figure 2
Figure 2. This figure illustrates both derivative graphs of [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

77 extracted references · 76 canonical work pages

  1. [1]

    David J. Aldous. The random walk construction of uniform spanning trees and uniform labelled trees. SIAM Journal on Discrete Mathematics, 3(4):450–465, 1990

    work page 1990

  2. [2]

    Karp, Richard J

    Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszlo Lovasz, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In20th Annual Symposium on Foundations of Computer Science (sfcs 1979), pages 218–223, 1979

    work page 1979

  3. [3]

    Sampling Arborescences in Parallel

    Nima Anari, Nathan Hu, Amin Saberi, and Aaron Schild. Sampling Arborescences in Parallel. In James R. Lee, editor,12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 83:1– 83:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

    work page 2021

  4. [4]

    Log-concave polynomials iv: approximate exchange, tight mixing times, and near-optimal sam- pling of forests

    Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, and Thuy-Duong Vuong. Log-concave polynomials iv: approximate exchange, tight mixing times, and near-optimal sam- pling of forests. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 408–420, New York, NY, USA, 2021. Association for Computing Machinery

    work page 2021

  5. [5]

    Parallel algorithms for geometric graph problems

    Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. STOC ’14, page 574–583, New York, NY, USA,

    work page

  6. [6]

    Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi

    Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi. An olog n/log log n-approximation algorithm for the asymmetric traveling salesman problem. Oper. Res., 65(4):1043–1061, aug 2017

    work page 2017

  7. [7]

    Fast personalized pagerank on mapre- duce

    Bahman Bahmani, Kaushik Chakrabarti, and Dong Xin. Fast personalized pagerank on mapre- duce. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD ’11, page 973–984, New York, NY, USA, 2011. Association for Computing Machinery

    work page 2011

  8. [8]

    Short random walks on graphs

    Greg Barnes and Uriel Feige. Short random walks on graphs. SIAM Journal on Discrete Mathematics, 9(1):19–28, 1996

    work page 1996

Show all 77 references
  1. [9]

    Communication steps for parallel query processing

    Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. J. ACM, 64(6), oct 2017

    2017

  2. [10]

    Near-optimal approximate shortest paths and transshipment in distributed and streaming models.SIAM Journal on Computing, 50(3):815–856, 2021

    Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph Lenzen. Near-optimal approximate shortest paths and transshipment in distributed and streaming models.SIAM Journal on Computing, 50(3):815–856, 2021. 29

    2021

  3. [11]

    Randomness-efficient oblivious sampling

    Mihir Bellare and John Rompel. Randomness-efficient oblivious sampling. InProceedings 35th Annual Symposium on Foundations of Computer Science, pages 276–287. IEEE, 1994

    1994

  4. [12]

    Generating random spanning trees

    Andrei Broder. Generating random spanning trees. In30th Annual Symposium on Foundations of Computer Science, pages 442–447, 1989

    1989

  5. [13]

    Broder and Anna R

    Andrei Z. Broder and Anna R. Karlin. Bounds on the cover time. In[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pages 479–487, 1988

    1988

  6. [14]

    Time and space optimal massively parallel algorithm for the 2-ruling set problem

    Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. Time and space optimal massively parallel algorithm for the 2-ruling set problem. In Rotem Oshman, editor,37th International Symposium on Distributed Computing, DISC 2023, October 10-12, 2023, L’Aquila, Italy, vol- ume ...

    2023

  7. [15]

    Improved Distributed Algorithms for Random Colorings

    Charlie Carlson, Daniel Frishberg, and Eric Vigoda. Improved Distributed Algorithms for Random Colorings. In Alysson Bessani, Xavier Défago, Junya Nakamura, Koichi Wada, and Yukiko Yamauchi, editors,27th International Conference on Principles of Distributed Systems (OPODIS 202...

    2023

  8. [16]

    Distributed subgraph finding: Progress and challenges, 2024

    Keren Censor-Hillel. Distributed subgraph finding: Progress and challenges, 2024

    2024

  9. [17]

    Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela

    Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. InProceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15, page 143–152, New York, NY, USA, 2015. Asso...

    2015

  10. [18]

    A. K. Chandra, P. Raghavan, W. L. Ruzzo, and R. Smolensky. The electrical resistance of a graph captures its commute and cover times. InProceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC ’89, page 574–586, New York, NY, USA, 1989. Association for...

    1989

  11. [19]

    Colbourn, Wendy J

    Charles J. Colbourn, Wendy J. Myrvold, and Eugene Neufeld. Two algorithms for unranking arborescences. Journal of Algorithms, 20(2):268–281, 1996

    1996

  12. [20]

    Simple, deterministic, constant-round coloring in the congested clique

    Artur Czumaj, Peter Davies, and Merav Parter. Simple, deterministic, constant-round coloring in the congested clique. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC ’20, page 309–318, New York, NY, USA, 2020. Association for Computing Machinery

    2020

  13. [21]

    Distributed random walks.J

    Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, and Prasad Tetali. Distributed random walks.J. ACM, 60(1), feb 2013

    2013

  14. [22]

    Tri, Tri Again

    Danny Dolev, Christoph Lenzen, and Shir Peled. “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting. InProceedings of the 26th International Symposium on Distributed Computing (DISC), pages 195–209, 2012

    2012

  15. [23]

    Random spanning trees for expanders, sparsifiers, and virtual network security.Computer Communications, 212:21–34, 2023

    Shlomi Dolev and Daniel Khankin. Random spanning trees for expanders, sparsifiers, and virtual network security.Computer Communications, 212:21–34, 2023

    2023

  16. [24]

    Exponentially faster shortest paths in the congested clique.J

    Michal Dory and Merav Parter. Exponentially faster shortest paths in the congested clique.J. ACM, 69(4), aug 2022. 30

    2022

  17. [25]

    On the power of the congested clique model

    Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC ’14, page 367–376, New York, NY, USA, 2014. Association for Computing Machinery

    2014

  18. [26]

    David Durfee, John Peebles, Richard Peng, and Anup B. Rao. Determinant-preserving sparsi- fication of sddm matrices.SIAM J. Comput., 49, 2020

    2020

  19. [27]

    Hayes, and Yitong Yin

    Weiming Feng, Thomas P. Hayes, and Yitong Yin. Distributed symmetry breaking in sampling (optimal distributed randomly coloring with fewer colors), 2018

    2018

  20. [28]

    Hayes, and Yitong Yin

    Weiming Feng, Thomas P. Hayes, and Yitong Yin. Distributed metropolis sampler with optimal parallelism. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, page 2121–2140, USA, 2021. Society for Industrial and Applied Math- ematics

    2021

  21. [29]

    What can be sampled locally? InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’17, page 121–130, New York, NY, USA, 2017

    Weiming Feng, Yuxin Sun, and Yitong Yin. What can be sampled locally? InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’17, page 121–130, New York, NY, USA, 2017. Association for Computing Machinery

    2017

  22. [30]

    On local distributed sampling and counting

    Weiming Feng and Yitong Yin. On local distributed sampling and counting. InProceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, page 189–198, New York, NY, USA, 2018. Association for Computing Machinery

    2018

  23. [31]

    A simple parallel and distributed sampling technique: Local glauber dynamics

    Manuela Fischer and Mohsen Ghaffari. A simple parallel and distributed sampling technique: Local glauber dynamics. In Ulrich Schmid and Josef Widder, editors,32nd International Sym- posium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, volume 1...

    2018

  24. [32]

    The laplacian paradigm in the broadcast congested clique

    Sebastian Forster and Tijn de Vos. The laplacian paradigm in the broadcast congested clique. InProceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, page 335–344, New York, NY, USA, 2022. Association for Computing Machinery

    2022

  25. [33]

    Harvey, and Debmalya Panigrahi

    Wai Shing Fung, Ramesh Hariharan, Nicholas J.A. Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. InProceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, page 71–80, New York, NY, USA, 2011. Association for Computing ...

    2011

  26. [34]

    Distributed MIS via all-to-all communication

    Mohsen Ghaffari. Distributed MIS via all-to-all communication. InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 141–149, 2017

    2017

  27. [35]

    Improved massively parallel computation algorithms for mis, matching, and vertex cover

    Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, and Ronitt Rubin- feld. Improved massively parallel computation algorithms for mis, matching, and vertex cover. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, E...

    2018

  28. [36]

    Congested clique algorithms for the minimum cut problem

    Mohsen Ghaffari and Krzysztof Nowicki. Congested clique algorithms for the minimum cut problem. InProceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, page 357–366, New York, NY, USA, 2018. Association for Computing Machinery. 31

    2018

  29. [37]

    MST in Log-Star Rounds of Congested Clique

    Mohsen Ghaffari and Merav Parter. MST in Log-Star Rounds of Congested Clique. InPro- ceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 19–28, 2016

    2016

  30. [38]

    A randomized rounding approach to the traveling salesman problem

    Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. A randomized rounding approach to the traveling salesman problem. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 550–559, 2011

    2011

  31. [39]

    Random minimum spanning trees, Oct 2018

    Christina Goldschmidt. Random minimum spanning trees, Oct 2018

    2018

  32. [40]

    Goodrich, Nodari Sitchinava, and Qin Zhang

    Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. InProceedings of the 22nd International Conference on Algorithms and Computation, ISAAC’11, page 374–383, Berlin, Heidelberg, 2011. Springer-Verlag

    2011

  33. [41]

    Expanders via random spanning trees

    Navin Goyal, Luis Rademacher, and Santosh Vempala. Expanders via random spanning trees. SODA ’09, page 576–585, USA, 2009. Society for Industrial and Applied Mathematics

    2009

  34. [42]

    Uniform sampling through the lovász local lemma

    Heng Guo, Mark Jerrum, and Jingcheng Liu. Uniform sampling through the lovász local lemma. J. ACM, 66(3), apr 2019

    2019

  35. [43]

    Nicholas J. A. Harvey and Keyulu Xu. Generating random spanning trees via fast matrix multiplication. In Latin American Symposium on Theoretical Informatics, 2016

    2016

  36. [44]

    Hegeman, Gopal Pandurangan, Sriram V

    James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato. Toward optimal bounds in the congested clique: Graph connectivity and mst. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15, pages 9...

    2015

  37. [45]

    Hegeman, Sriram V

    James W. Hegeman, Sriram V. Pemmaraju, and Vivek Sardeshmukh. Near-constant-time dis- tributed algorithms on a congested clique. In Fabian Kuhn, editor,Distributed Computing - 28th International Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceed- ings, volume ...

    2014

  38. [46]

    A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.J

    Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.J. ACM, 51(4):671–697, jul 2004

    2004

  39. [47]

    Valiant, and Vijay V

    Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution.Theor. Comput. Sci., 43:169–188, 1986

    1986

  40. [48]

    Mst in o(1) rounds of congested clique

    Tomasz Jurdziński and Krzysztof Nowicki. Mst in o(1) rounds of congested clique. InProceed- ings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, pages 2620–2632, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathemat- ics

    2018

  41. [49]

    Karlin, Nathan Klein, and Shayan Oveis Gharan

    Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric tsp. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 32–45, New York, NY, USA, 2021. Association for Computing Machinery

    2021

  42. [50]

    Karlin, Nathan Klein, Shayan Oveis Gharan, and Xinzhi Zhang

    Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, and Xinzhi Zhang. An improved approx- imation algorithm for the minimum k-edge connected multi-subgraph problem. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 1612–1620, New York...

    2022

  43. [51]

    A model of computation for mapre- duce

    Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapre- duce. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algo- rithms, SODA ’10, page 938–948, USA, 2010. Society for Industrial and Applied Mathematics

    2010

  44. [52]

    Kelner and Aleksander Madry

    Jonathan A. Kelner and Aleksander Madry. Faster generation of random spanning trees. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 13–21, 2009

    2009

  45. [53]

    Kirby, Roger B

    Edward C. Kirby, Roger B. Mallion, Paul Pollak, and Pawel Skrzynski. What kirchhoff actually did concerning spanning trees in electrical networks and its relationship to modern graph- theoretical work.Croatica Chemica Acta, 89, 2016

    2016

  46. [54]

    Distributed Computation of Large-scale Graph Problems

    Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. Distributed Computation of Large-scale Graph Problems. InProceedings of the Twenty-Sixth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 391–410, 2015

    2015

  47. [55]

    Approximate Gaussian Elimination

    Rasmus Kyng. Approximate Gaussian Elimination. PhD thesis, 2017

    2017

  48. [56]

    Optimal deterministic routing and sorting on the congested clique

    Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC ’13, page 42–50, New York, NY, USA, 2013. Association for Computing Machinery

    2013

  49. [57]

    Walking randomly, massively, and efficiently

    Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski. Walking randomly, massively, and efficiently. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 364–377, New York, NY, USA, 2020. Association for Computing Machinery

    2020

  50. [58]

    Mst construction in o(log log n) communication rounds

    Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. Mst construction in o(log log n) communication rounds. In Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’03, page 94–100, New York, NY, USA, 2003. Association for Com...

    2003

  51. [59]

    Random walks on graphs: A survey

    László Lovász. Random walks on graphs: A survey. 1993

    1993

  52. [60]

    Distributed pagerank computation: an improved theoretical study

    Siqiang Luo. Distributed pagerank computation: an improved theoretical study. InProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Adv...

    2019

  53. [61]

    Distributed pagerank computation with improved round complexities

    Siqiang Luo, Xiaowei Wu, and Ben Kao. Distributed pagerank computation with improved round complexities. Information Sciences, 607:109–125, 2022

    2022

  54. [62]

    Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding

    Russell Lyons and Shayan Oveis Gharan. Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding. International Mathematics Research Notices, 2018(24):7555–7605, 05 2017

    2018

  55. [63]

    From graphs to matrices, and back: new techniques for graph algorithms

    Aleksander Mądry. From graphs to matrices, and back: new techniques for graph algorithms. PhD thesis, Massachusetts Institute of Technology, 2011

    2011

  56. [64]

    Fast generation of random span- ning trees and the effective resistance metric

    Aleksander Mądry, Damian Straszak, and Jakub Tarnawski. Fast generation of random span- ning trees and the effective resistance metric. InProceedings of the Twenty-Sixth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA ’15, page 2019–2036, USA, 2015. Society for Industr...

    2019

  57. [65]

    A deterministic algorithm for the mst problem in constant rounds of con- gested clique

    Krzysztof Nowicki. A deterministic algorithm for the mst problem in constant rounds of con- gested clique. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1154–1165, New York, NY, USA, 2021. Association for Comput- ing Machinery

    2021

  58. [66]

    Congested clique algorithms for graph spanners

    Merav Parter and Eylon Yogev. Congested clique algorithms for graph spanners. In32nd Inter- national Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, volume 121 ofLIPIcs, pages 40:1–40:18, 2018

    2018

  59. [67]

    Pemmaraju and Vivek B

    Sriram V. Pemmaraju and Vivek B. Sardeshmukh. Super-fast MST algorithms in the congested clique using o(m) messages. In Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen, editors, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Com- puter ...

    2016

  60. [68]

    Pemmaraju and Joshua Z

    Sriram V. Pemmaraju and Joshua Z. Sobel. Exact distributed sampling. page 558–575, Berlin, Heidelberg, 2023. Springer-Verlag

    2023

  61. [69]

    An almost-linear time algorithm for uniform random spanning tree generation

    Aaron Schild. An almost-linear time algorithm for uniform random spanning tree generation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 214–227, New York, NY, USA, 2018. Association for Computing Machinery

    2018

  62. [70]

    Independent sets versus perfect matchings.Theoretical Computer Science, 145(1):381–390, 1995

    Shang-Hua Teng. Independent sets versus perfect matchings.Theoretical Computer Science, 145(1):381–390, 1995

    1995

  63. [71]

    Pseudorandomness.Foundations and Trends® in Theoretical Computer Sci- ence, 7(1–3):1–336, 2012

    Salil P Vadhan. Pseudorandomness.Foundations and Trends® in Theoretical Computer Sci- ence, 7(1–3):1–336, 2012

    2012

  64. [72]

    New bounds for ma- trix multiplication: from alpha to omega

    Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for ma- trix multiplication: from alpha to omega. InACM-SIAM Symposium on Discrete Algorithms, 2023

    2023

  65. [73]

    Generating random spanning trees more quickly than the cover time

    David Bruce Wilson. Generating random spanning trees more quickly than the cover time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 296–303, New York, NY, USA, 1996. Association for Computing Machinery. 34 5 Appendix: Exactly ...

    1996

  66. [75]

    This results in an arbitrary spanning tree being returned

    The first source of error arises because there may be a phase where a walk fails to visitΩ(√n) distinct vertices. This results in an arbitrary spanning tree being returned

  67. [76]

    The second source of error arises from using approximate probabilities rather than true prob- abilities to generate midpoints

  68. [77]

    5.1 Solving Problem 1 The clear solution to the first problem is to convert the algorithm from a Monte Carlo to Las Vegas approach

    Finally, the third source of error arises from using approximate matching sampling rather than exact matching sampling and approximate probabilities in the matching algorithm. 5.1 Solving Problem 1 The clear solution to the first problem is to convert the algorithm from a Mont...

  69. [2014]

    Association for Computing Machinery

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.