Distributed Sparsest Cut via Eigenvalue Estimation

Tijn de Vos; Yannic Maus

REVIEW 3 major objections 4 minor 10 references

Distributed Sparsest Cut via Eigenvalue Estimation

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

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

Pith's one-line read Distributed spectral method approximates sparsest cut to Cheeger-limit quality in O(log² n/φ) rounds.

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

arxiv 2508.19898 v2 pith:V357KNMY submitted 2025-08-27 cs.DS

Yannic Maus , Tijn de Vos This is my paper · ORCID

classification cs.DS MSC 68W1505C50

keywords sparsestcutconductancenormalizedLaplacianeigenvalueestimationCONGESTmodelpowermethodCheeger'sinequalityk-way

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the 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.

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

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

Net: 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.

Referee Report

3 major / 4 minor

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.

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 (3)

[Section 3.1, proof of Theorem 1] 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 2.4, Claim 2] 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 1.1 and 3.1, interpretation of Cheeger's Inequality] 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.

minor comments (4)

[Section 2.4, Claim 2 proof] 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 1.1] 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 3.3] There are repeated typos: 'sparest cut' should be 'sparsest cut'; 'sparsity1/n and 1/n2' should be formatted consistently.
[Appendix A.2, Lemma 11 proof] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: spectral derivation uses external Cheeger/power-method theorems; self-citations are not load-bearing; proof gaps are correctness issues, not circularity.

full rationale

The derivation chain is: (i) the power method (Lemma 7, with a self-contained proof in Appendix A) approximates the largest eigenvalue of a PSD matrix; (ii) the standard transformation M=2I-L moves lambda_2 to the top of the spectrum, with periodic orthogonalization against the exactly known eigenvector sqrt(deg); (iii) Theorem 5 yields tilde_lambda_2 in [lambda_2, lambda_2 + epsilon]; (iv) Cheeger's Inequality (Theorem 8) and the higher-order Cheeger inequality (Theorem 9) are then used in the forward direction to convert eigenvalue estimates into conductance estimates. None of these steps defines the output in terms of the target quantity or fits a parameter to the target data. The choice delta=0.005*phi and the exponential search over phi is a standard guess-and-check for an unknown optimum, not a fit that forces the bound. Self-citations ([Vos23], [FV22], [FV23]) appear only in Related Work and are not used in the proofs; no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in via citation. I therefore find no circularity. Non-circular correctness issues are present and should be flagged separately. In the proof of Theorem 1 (Section 3.1), the step 'tilde_phi <= sqrt(2*lambda_2 + 2*delta) <= sqrt(2*phi + 2*delta)' uses lambda_2 <= phi, whereas Cheeger's inequality only gives lambda_2 <= 2*phi, and the factor of 2 is generally tight; the claimed sqrt(2.01*phi) guarantee is therefore not established by the written argument. In Claim 2 (Section 2.4), the bound (2/(2-lambda_2))^l <= (1+lambda_2)^l is false for lambda_2 > 1, so the stability analysis requires an unstated bound on lambda_2. These are mathematical/stability gaps, not circular reductions: the outputs are not equal to the inputs by construction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard spectral graph theory (Cheeger, higher-order Cheeger, Weyl), on the existence of certain high-conductance graphs from prior work, and on CONGEST model conventions. No numerical parameters are fitted to data: eps and delta are accuracy targets, and the delta = 0.005 phi setting is handled by exponential search. No new physical or mathematical entities are introduced.

assumptions (5)

standard math Cheeger's Inequality (Theorem 8) relating lambda_2 and conductance phi
Used to convert the approximate second eigenvalue into a conductance approximation; cited to AM85, Alo86, SJ89 and not proven in the paper.
standard math Higher-order Cheeger's Inequality (Theorem 9) for k-way conductance
Used to turn approximate lambda_k into an approximation of k-way conductance; cited to LGT12.
standard math Weyl's Inequality for symmetric matrices
Used in Section 2.5.1 to bound the eigenvalue shift between Mideal and Mapprox; cited to HJ12.
domain assumption Existence of graphs with conductance phi and diameter Theta(log n / phi) from CGLP18
Used in the proof of Theorem 4, the lower bound for most values of phi; assumed from prior literature.
domain assumption CONGEST model conventions: vertices know n and their weighted degree, and the communication graph equals the input graph
Standard assumptions of the model used throughout the algorithms and lower bounds.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Distributed Sparsest Cut via Eigenvalue Estimation." pith.science (2026). https://pith.science/paper/V357KNMY

@misc{pith2026250819898,
  author       = {Pith},
  title        = {Pith review of: Distributed Sparsest Cut via Eigenvalue Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V357KNMY}},
  note         = {Machine review of arXiv:2508.19898}
}

abstract

We give new, improved bounds for approximating the sparsest cut value or in other words the conductance $\phi$ of a graph in the CONGEST model. As our main result, we present an algorithm running in $O(\log^2 n/\phi)$ rounds in which every vertex outputs a value $\tilde \phi$ satisfying $\phi \le \tilde \phi \le \sqrt{2.01\phi}$. In most regimes, our algorithm improves significantly over the previously fastest algorithm for the problem [Chen, Meierhans, Probst Gutenberg, Saranurak; SODA 25]. Additionally, our result generalizes to $k$-way conductance. We obtain these results, by approximating the eigenvalues of the normalized Laplacian matrix $L:=I-{\rm Deg}^{-1/2}A{\rm Deg}^ {-1/2}$, where, $A$ is the adjacency matrix and Deg is the diagonal matrix with the weighted degrees on the diagonal. We show our algorithms are near-optimal by proving a lower bound for computing the smallest non-trivial eigenvalue of $L$, even in the stronger LOCAL model The previous state of the art sparsest cut algorithm is in the technical realm of expander decompositions. Our algorithms, on the other hand, are relatively simple and easy to implement. At the core, they rely on the well-known power method, which comes down to repeatedly multiplying the Laplacian with a vector. This operation can be performed in a single round in the CONGEST model. All our algorithms apply to weighted, undirected graphs. Our lower bounds apply even in unweighted graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 7 canonical work pages

[16]

We investigate the numerical stability of this case

In which case the power method gives a good approximation. We investigate the numerical stability of this case. We need to compare before and after rounding for (xk)T M xk (xk)T xk = xT 0 M 2k+1x0 x0M 2kx0 = xT i M 2l+1xi xiM 2lxi , where l := k − i. Denote the difference occurred by rounding asy, i.e., after rounding we have xi + y and since we round aft...

work page
[55]

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal

doi: 10.1137/1.9781611977585.CH5 . url: https://doi.org/10.1137/1. 9781611977585.ch5 (cit. on p. 1). [CKKR+06] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivaku- mar. “On the Hardness of Approximating Multicut and Sparsest-Cut”. In:Com- put. Complex. 15.2 (2006). Announced at CCC’05, pp. 94–114.doi: 10.1007/ S00037- 006- 0210- 9. ...

work page Pith review arXiv 2006
[226]

A decentralized algorithm for spectral anal- ysis

arXiv: 1304.2338 (cit. on p. 6). [KM08] David Kempe and Frank McSherry. “A decentralized algorithm for spectral anal- ysis”. In:J. Comput. Syst. Sci.74.1 (2008). Announced at STOC’04, pp. 70–83. doi: 10.1016/J.JCSS.2007.04.014. url: https://doi.org/10.1016/j.jcss. 2007.04.014 (cit. on p. 4). [KM15] Fabian Kuhn and Anisur Rahaman Molla. “Distributed Sparse...

arXiv 2008
[262]

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

arXiv: 1307.2205 (cit. on p. 6). [M1 ˛6] AleksanderMądry.“ComputingMaximumFlowwithAugmentingElectricalFlows”. In: Proc. of the IEEE 57th Annual Symposium on Foundations of Computer Sci- ence, FOCS 2016. IEEE Computer Society, 2016, pp. 593–602. arXiv:1608.06016 (cit. on p. 6). [MMM18] Frederik Mallmann-Trenn, Cameron Musco, and Christopher Musco. “Eigenve...

work page Pith review arXiv 2016
[335]

Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators

arXiv: 1911.01956 (cit. on p. 6). [BCMN+18] LucaBecchetti,AndreaClementi,PasinManurangsi,EmanueleNatale,Francesco Pasquale,PrasadRaghavendra,andLucaTrevisan.“AverageWheneverYouMeet: Opportunistic Protocols for Community Detection”. In:26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland. Ed. by Yossi Azar, Hannah B...

work page Pith review arXiv 1911
[2013]

Distributed Verifi- cation and Hardness of Distributed Approximation

IEEE Computer Society, 2013, pp. 263–269. arXiv:1304.2077 (cit. on p. 6). [SHKK+12] Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. “Distributed Verifi- cation and Hardness of Distributed Approximation”. In:SIAM J. Comput.41.5 (2012).AnnouncedatSTOC’11,pp.1235–1265. doi: 10....

arXiv 2013
[2015]

Minimum Cost Flow in the CONGEST Model

url: https : / / theory . stanford . edu / ~trevisan / expander - online / lecture03.pdf (cit. on p. 31). 29 [Vos23] Tijn de Vos. “Minimum Cost Flow in the CONGEST Model”. In: Structural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6-9, 2023, Proceedings. Ed. by Sergio Rajsbaum, Alk...

work page Pith review arXiv 2023
[2017]

New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms

Ed. by Elad Michael Schiller and Alexander A. Schwarzmann. ACM, 2017, 26 pp. 131–140.doi: 10.1145/3087801.3087827. url: https://doi.org/10.1145/ 3087801.3087827 (cit. on p. 1). [GL18] Mohsen Ghaffari and Jason Li. “New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms”. In:32nd International Sym- posium on Distribut...

arXiv 2017

Show all 10 references

[2020]

Multi-way dual Cheeger constants and spectral bounds of graphs

ACM, 2020, pp. 308–321. arXiv:1911.01626 (cit. on p. 6). [Liu15] Shiping Liu. “Multi-way dual Cheeger constants and spectral bounds of graphs”. In: Advances in Mathematics268 (2015), pp. 306–338. arXiv:1401.3147 (cit. on p. 3). [LMR18] Reut Levi, Moti Medina, and Dana Ron. “Pr...

2020 arXiv
[2022]

Eigenvalues and expanders

Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, 6:1–6:20. arXiv: 2109.05151 (cit. on p. 6). [Alo86] Noga Alon. “Eigenvalues and expanders”. In: Comb. 6.2 (1986), pp. 83–96.doi: 10.1007/BF02579166 . url: https://doi.org/10.1007/BF02579166 (cit. on pp. 2, 10). [AM85] No...

2022 arXiv

Pith tools

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

[1] [16]

We investigate the numerical stability of this case

In which case the power method gives a good approximation. We investigate the numerical stability of this case. We need to compare before and after rounding for (xk)T M xk (xk)T xk = xT 0 M 2k+1x0 x0M 2kx0 = xT i M 2l+1xi xiM 2lxi , where l := k − i. Denote the difference occurred by rounding asy, i.e., after rounding we have xi + y and since we round aft...

work page

[2] [55]

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal

doi: 10.1137/1.9781611977585.CH5 . url: https://doi.org/10.1137/1. 9781611977585.ch5 (cit. on p. 1). [CKKR+06] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivaku- mar. “On the Hardness of Approximating Multicut and Sparsest-Cut”. In:Com- put. Complex. 15.2 (2006). Announced at CCC’05, pp. 94–114.doi: 10.1007/ S00037- 006- 0210- 9. ...

work page Pith review arXiv 2006

[3] [226]

A decentralized algorithm for spectral anal- ysis

arXiv: 1304.2338 (cit. on p. 6). [KM08] David Kempe and Frank McSherry. “A decentralized algorithm for spectral anal- ysis”. In:J. Comput. Syst. Sci.74.1 (2008). Announced at STOC’04, pp. 70–83. doi: 10.1016/J.JCSS.2007.04.014. url: https://doi.org/10.1016/j.jcss. 2007.04.014 (cit. on p. 4). [KM15] Fabian Kuhn and Anisur Rahaman Molla. “Distributed Sparse...

arXiv 2008

[4] [262]

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

arXiv: 1307.2205 (cit. on p. 6). [M1 ˛6] AleksanderMądry.“ComputingMaximumFlowwithAugmentingElectricalFlows”. In: Proc. of the IEEE 57th Annual Symposium on Foundations of Computer Sci- ence, FOCS 2016. IEEE Computer Society, 2016, pp. 593–602. arXiv:1608.06016 (cit. on p. 6). [MMM18] Frederik Mallmann-Trenn, Cameron Musco, and Christopher Musco. “Eigenve...

work page Pith review arXiv 2016

[5] [335]

Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators

arXiv: 1911.01956 (cit. on p. 6). [BCMN+18] LucaBecchetti,AndreaClementi,PasinManurangsi,EmanueleNatale,Francesco Pasquale,PrasadRaghavendra,andLucaTrevisan.“AverageWheneverYouMeet: Opportunistic Protocols for Community Detection”. In:26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland. Ed. by Yossi Azar, Hannah B...

work page Pith review arXiv 1911

[6] [2013]

Distributed Verifi- cation and Hardness of Distributed Approximation

IEEE Computer Society, 2013, pp. 263–269. arXiv:1304.2077 (cit. on p. 6). [SHKK+12] Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. “Distributed Verifi- cation and Hardness of Distributed Approximation”. In:SIAM J. Comput.41.5 (2012).AnnouncedatSTOC’11,pp.1235–1265. doi: 10....

arXiv 2013

[7] [2015]

Minimum Cost Flow in the CONGEST Model

url: https : / / theory . stanford . edu / ~trevisan / expander - online / lecture03.pdf (cit. on p. 31). 29 [Vos23] Tijn de Vos. “Minimum Cost Flow in the CONGEST Model”. In: Structural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6-9, 2023, Proceedings. Ed. by Sergio Rajsbaum, Alk...

work page Pith review arXiv 2023

[8] [2017]

New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms

Ed. by Elad Michael Schiller and Alexander A. Schwarzmann. ACM, 2017, 26 pp. 131–140.doi: 10.1145/3087801.3087827. url: https://doi.org/10.1145/ 3087801.3087827 (cit. on p. 1). [GL18] Mohsen Ghaffari and Jason Li. “New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms”. In:32nd International Sym- posium on Distribut...

arXiv 2017