Pith. sign in

REVIEW 3 major objections 6 minor 23 references

Parallel Spectral Graph Sparsification via Low Diameter Decompositions

T0 review · 3 major / 6 minor · reviewed 2026-07-31 · grok-4.5

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

Pith's one-line read A parallel spectral sparsifier built only from low-diameter decompositions removes all dependence on accuracy ε from work and depth.

desk verdict Solid LDD-based estimator that really removes ε from work/depth; one unstated min-weight normalization is needed for the imported resistance bound, but the core idea is clean and worth engaging. read the letter →

arxiv 2607.25059 v1 pith:5J6XZ2OX submitted 2026-07-27 cs.DS cs.DC

Yves Baumann , Gernot Zöcklein This is my paper · ORCID
classification cs.DScs.DC MSC 68W1005C8568R1065F08
keywords spectralsparsificationlow-diameterdecompositionrobustconnectivityparallelalgorithmseffectiveresistanceLaplacianpreconditioningsolver-free
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

Spectral sparsifiers replace a dense weighted graph by a much sparser one that still approximates every quadratic form of the Laplacian, which is the key primitive behind fast Laplacian solvers and parallel approximate Cholesky. Prior solver-free parallel methods either needed heavy distance oracles or paid an ε⁻² factor in both work and depth, which becomes costly when the target accuracy is 1/log n. This paper shows that robust connectivities—probabilities that two endpoints stay close after random edge sub-sampling—can be estimated by running ordinary low-diameter decompositions on a logarithmic number of independently thinned copies of the graph. Edges whose endpoints repeatedly land in the same cluster receive small sampling probabilities; the rest are kept more often. The resulting algorithm produces a (1±ε)-sparsifier with O(n ε⁻² log³ n) edges in work O(m log n log(nW)) and depth O(log² n log* n), with no ε factor in the resource bounds. Experiments on grid Laplacians after partial Cholesky fill-in show the practical leverage-score heuristic cuts PCG iterations by roughly 4–5× versus weight-based baselines at the same edge budget.

What carries the argument

The Robust Connectivity Decide procedure (Algorithm 1 / Lemma 3.1): for a candidate density π it runs O(log n) LDDs on independent copies of G_π and keeps an edge when the fraction of trials in which its endpoints share a cluster exceeds 8.5/16; this cleanly separates edges with q_κ(e) ≤ π/4 from those with q_{4κα_LDD}(e) ≥ π, enabling a geometric search for usable resistance overestimates.

What would settle it

Run the decide procedure on a family of graphs with known robust connectivities (or exact effective resistances) and check whether the empirical same-cluster frequencies still fall cleanly above 8.5/16 precisely when q_κ(e) ≤ π/4 and below it when q_{4κα_LDD}(e) ≥ π; a systematic misclassification at moderate n would refute the lemma.

Watch

Extended reading notes

Core claim

Robust connectivities of a weighted graph can be estimated well enough for spectral sparsification by nothing more than independent edge sub-sampling and parallel low-diameter decompositions: if endpoints often share an LDD cluster across O(log n) thinned copies at geometrically decreasing densities, the edge’s robust connectivity (hence an upper bound on its effective resistance) is small, and sampling according to those estimates yields a (1±ε) sparsifier whose construction work and depth are independent of ε.

Load-bearing premise

The method needs the probability that two nearby vertices land in the same low-diameter cluster, and the probability that two far vertices do not, to sit on opposite sides of a fixed numerical threshold after a constant number of random thinnings; if real LDD diameters or the two-copy coupling are much worse than the analysis assumes, the separation fails.

Editorial extensions

If this is right

  • Parallel approximate-Cholesky frameworks that call a black-box sparsifier O(log n) times at accuracy ε/log n no longer inherit an extra ε⁻² (hence log² n) blow-up in depth or work.
  • Any downstream routine whose bottleneck was solver-free parallel sparsification can now treat work and depth as essentially independent of the final approximation quality.
  • The same LDD-based estimator supplies the scores for a practical one-shot max-tree-plus-leverage sparsifier that measurably reduces PCG iterations on filled-in grid Laplacians.
  • Because the only primitives are LDDs, MSTs and independent sampling, the construction is immediately portable to existing parallel graph libraries.

Reading between the lines

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

  • Dynamic or batch-dynamic LDD data structures would likely turn the same estimator into a parallel batch-dynamic sparsifier, a direction the authors flag but do not develop.
  • The ε-independence makes the method especially attractive inside nested dissection or multilevel schemes that repeatedly request finer and finer sparsifiers.
  • If the same cluster-frequency statistic can be shown to control directed or Eulerian effective resistances, the technique might extend to the directed Laplacian setting where practical sparsifiers are still scarce.
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.

Referee Report

3 major / 6 minor

Summary. The paper presents a solver-free parallel algorithm for spectral sparsification of weighted graphs. Following Kapralov–Panigrahy (KP12), edges are sampled according to (over-estimates of) their robust connectivities q_κ(e). The new technical contribution is a method for estimating q_κ(e) that replaces approximate distance oracles by low-diameter decompositions (LDDs): for O(log nW) geometrically spaced sampling rates π, the algorithm samples t = O(log n) copies of G_π, runs a parallel LDD on each, and uses the fraction of trials in which an edge's endpoints share a cluster as a decision statistic Z_e. Lemma 3.1 shows the threshold 8.5/16 separates the regimes q_κ(e) ≤ π/4 and q_{4κα_LDD}(e) ≥ π w.h.p.; a binary search (Lemma 3.2) yields q̂(e) with q_{4κα_LDD}(e) ≤ q̂(e) ≤ 8q_κ(e); Lemma 3.3 converts these to effective-resistance over-estimates with total weight O(n log² n); Theorem 3.4 then applies Spielman–Srivastava sampling to obtain a (1±ε) sparsifier with O(n ε^{-2} log³ n) edges in work O(m log n log nW) and depth O(log² n log* n), with no ε-dependence in the estimation phase. Experiments on eliminated 2D/3D grid graphs show a heuristic variant (max-score spanning tree backbone plus budgeted leverage sampling) beating weight-based baselines by 4–5× in PCG iterations. I verified the new technical pieces: Claim 2.8's stochastic domination holds (Pr[f ∈ H] = 1-(1-p'_f)² ≤ min{w_f π, 1} in all cases, with edgewise independence giving the monotone coupling; the boundary q_κ(

Significance. If the normalization gap (Major Comment 1) is fixed, this is a strong contribution. It gives the first solver-free parallel spectral sparsification algorithm whose estimation work and depth carry no ε^{-2} factor — an asymptotic and conceptual improvement over Koutis (2014) and its refinements, and a clean plug-in for the parallel approximate-Cholesky framework of [3]. The two structural insights (distance estimation is only needed at a two-scale threshold; an LDD same-cluster indicator is correct in expectation, avoiding a log-factor amplification) are simple, well motivated, and likely reusable. The paper also ships a working parallel implementation on GBBS with experiments showing 4-5× improvements in PCG iteration counts over weight-based baselines at matched edge budgets, with wall-clock data in Appendix A.2 supporting the iteration-count proxy. The result is falsifiable, the analysis is largely self-contained, and the constants are explicit. I note explicitly that the stress-test concern about Claim 2.8 does not land; the genuinely soft point is the imported Lemma 2.5, not the new material.

major comments (3)
  1. [Lemma 2.5 (§2.2), Algorithm 2 line 8, Theorem 3.4] Lemma 2.5 is quoted from [8] as R_e <= 2κ·q_κ(e) with no weight restriction, but as stated it is false, and the failure propagates into the main theorem. Counterexample: let e be a bridge of weight ε < 1/(2κ). Since the only u-v path is e itself, p_κ(e,η) = 1 - εη >= 1/2 for all η in [0,1], so q_κ(e) = 1, while R_e = 1/ε > 2κ. Kapralov-Panigrahy require a unit-minimum-weight normalization (consistent with this paper's experiments, min weight 1, and with the log nW work bound, which otherwise should be a log of the weight ratio). The failure is not cosmetic: for such an edge, Item 2 of Lemma 3.1 never guarantees inclusion (q_κ = 1 > π_i/4 for all i) and Item 1 forces exclusion everywhere, so j_e = max{i : e in Ẽ(i)} in Algorithm 2, line 8 is empty and bq(e) — hence bR_e — is undefined; any default <= 1 gives bR_e <= 8κα_LDD << R_e = 1/ε, so this leverage-score-1 edge is undersampled and t
  2. [Lemma 3.2 / Algorithm 2, lines 7-11] Even after imposing the normalization w_e >= 1, the proof of Lemma 3.2 silently assumes j_e exists for every edge, and this need not hold: an edge with q_κ(e) > 1/4 and q_{4κα_LDD}(e) < 1 falls in the gap region of Algorithm 1 at every π_i (Item 2 never forces inclusion, Item 1 only forces exclusion at small π_i), so it can be excluded from all Ẽ(i), leaving j_e and bq(e) undefined. A one-line fix suffices — e.g., set bq(e) = 1 (equivalently j_e = -1 with π = 2) for such edges, which is a valid over-estimate since R_e <= 2κ·q_κ(e) <= 2κ <= 8κα_LDD·1 — but the algorithm and the proof currently do not specify any default, and the claimed guarantee bR_e >= R_e in Lemma 3.3 has no content for edges where bR_e is undefined. Please add the default rule and the two-sentence argument that it preserves both bounds of Lemma 3.3.
  3. [Abstract, §1, Theorem 3.4] The abstract and §1 claim the algorithm 'eliminates any dependence on the target approximation accuracy ε in the algorithm's work and depth.' This is literally false for the total work: the output itself has Θ(n ε^{-2} log^3 n) edges in expectation, so writing the sparsifier costs Ω(n ε^{-2}) work (capped at m). The correct and still strong statement is that the ε^{-2} factor appears only in the output size and the final independent-sampling step, not as a multiplicative overhead in the estimation work/depth — in contrast to [9,13], whose work and depth scale with ε^{-2}. As written, a reader comparing against Theorem 3.4's stated work bound O(m log n log nW) will notice the discrepancy. Please qualify the claim in the abstract, §1, and the 'Our Contribution' paragraph.
minor comments (6)
  1. [Proofs of Lemmas 3.1, 3.2] Broken cross-references: the proofs contain '??2.10' (proof of Lemma 3.1), '??2.8' (Lemma 3.1), and '??2.7' (Lemma 3.2). Also inconsistent capitalization of 'algorithm 1'/'theorem 2.1' versus 'Algorithm 2'/'Theorem 3.4' throughout.
  2. [§1 vs §2.2; Theorem 2.2] Notation collisions: κ denotes the condition number in §1 and the robust-connectivity parameter from Definition 2.3 onward; c denotes the generic constant in Theorem 2.2 and the oversampling constant of Theorem 2.1 (Algorithm 2, line 14). Consider renaming one of each pair.
  3. [Tables 1-2 (§4.5.1)] Tables 1 and 2: the 'Unif.' column is entirely em dashes and the 'Lev.' column has starred failures; a one-line explanation that uniform (and often pure leverage-score) sampling disconnects the graph, driving the condition number to infinity, would save readers from inferring a data error.
  4. [Remark 4.1] Remark 4.1 concludes a '1/2-approximate spectral sparsifier'; state explicitly that this corresponds to instantiating Theorem 2.1 at ε = 1/2 and give the resulting constant c_1 relation.
  5. [§5] §5 states that the algorithm 'immediately improves the depth and work of the parallelization framework' of [3]; an explicit corollary with the resulting work/depth numbers for parallel approximate Cholesky would make this application claim checkable.
  6. [§2 Notation; Claim 2.7] After the normalization fix (Major Comment 1), define the weight ratio (e.g., W_ratio = w_max/w_min) in the Notation paragraph; W is currently defined as max weight only, and Claim 2.7's bound 1/(4mW) should be restated accordingly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: standard algorithmic reduction from external robust-connectivity and LDD primitives to sparsifier sampling.

full rationale

The load-bearing chain is Theorem 2.1 (Spielman–Srivastava effective-resistance sampling) plus Lemmas 2.5–2.6 (Kapralov–Panigrahy robust connectivity bounds) plus an LDD-based estimator (Lemma 3.1 / Claims 2.8–2.10 / Thm 2.11 Miller–Peng–Xu) that binary-searches q_κ and feeds overestimates bR_e into independent sampling (Thm 3.4). None of these steps defines the target sparsifier quality in terms of itself, fits a parameter to the quantity being predicted, or rests on a uniqueness/ansatz result whose only support is overlapping-author citation. Self-citations ([3], [7]) appear only as application context for parallel approximate Cholesky and do not underwrite the sparsification proof. The experimental heuristic (Alg. 3) is explicitly presented as a practical variant, not as a derivation of the theorem. Correctness concerns about the imported Lemma 2.5 for sub-unit weights are orthogonal to circularity. Derivation is self-contained against external benchmarks; score 0.

Assumptions & free parameters 4 free parameters · 5 assumptions · 1 invented entities

The result rests on standard PRAM/CRCW model assumptions, classical effective-resistance sampling, Kapralov–Panigrahy robust connectivity, and the existence of efficient parallel (β, O(log n/β))-LDDs. No physical constants or data-fitted scales enter the theory. The practical heuristic introduces a free sparsity budget f and several hand-chosen experimental constants.

free parameters (4)
  • sparsity budget f (Algorithm 3) = 0.25 default; swept in Fig. 2
    Target fraction of edges retained in the practical one-shot sparsifier; set to 0.25 (and varied) in experiments, not derived.
  • κ = Θ(log n) and Chernoff trial count t = c log n
    Chosen large enough for high-probability union bounds and for the n^{O(1/κ)} term in Lemma 2.6 to become O(n); constants c are existential.
  • decision threshold 8.5/16 in Algorithm 1 = 8.5/16
    Hand-placed between the analytic means 9/16 and 1/2 with 1/32 Chernoff slack; works for the proof but is an analysis choice.
  • experimental grid weights and elimination fraction k = w_max=1e5, k∈{0.3,0.5}
    Checkerboard weights 1 vs 1e5, patch 4^d, k=0.5 (2D) / 0.3 (3D) chosen to create hard fill-in instances; not predicted by theory.
assumptions (5)
  • standard math Spielman–Srivastava independent sampling by leverage scores yields a (1±ε) spectral sparsifier whp when p_e ≥ c w_e R_e log n / ε² (Thm 2.1).
    Invoked at the final sampling step of Thm 3.4 and Remark 4.1.
  • domain assumption R_e ≤ 2κ · q_κ(e) and ∑_e w_e q_κ(e) ≤ 2 n^{1+O(1/κ)} (Kapralov–Panigrahy Lemmas 2–3).
    Load-bearing bridge from robust connectivity estimates to effective-resistance oversampling (Lemmas 2.5–2.6, used in 3.3).
  • domain assumption There exist parallel (β, α_LDD β⁻¹)-LDDs with α_LDD = O(log n), O(β⁻¹ log n log* n) depth and O(m) work (Miller–Peng–Xu / Miller–Peng–Vladu–Xu).
    Thm 2.11; every call in Algorithm 1 depends on diameter and deletion-probability guarantees.
  • domain assumption CRCW PRAM model for work/depth accounting.
    Stated in §2 Parallel Model; all resource claims are in this model.
  • ad hoc to paper Union of two independent G_{π/4} samples is stochastically edgewise dominated by G_π (Claim 2.8).
    Proved in-paper but essential for the one-sided robust-connectivity test; if the coupling fails under min{w_e p,1} sampling the separation collapses.
invented entities (1)
  • LDD-based robust-connectivity decision statistic Z_e independent evidence
    purpose: Replace approximate distance oracles when testing whether q_κ(e) is above or below a threshold π.
    Defined in Algorithm 1 as the empirical fraction of LDD trials where endpoints share a cluster; not a physical entity, but the paper’s central algorithmic object.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parallel Spectral Graph Sparsification via Low Diameter Decompositions." pith.science (2026). https://pith.science/paper/5J6XZ2OX

@misc{pith2026260725059,
  author       = {Pith},
  title        = {Pith review of: Parallel Spectral Graph Sparsification via Low Diameter Decompositions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5J6XZ2OX}},
  note         = {Machine review of arXiv:2607.25059}
}
abstract

We present a new solver-free parallel spectral sparsification algorithm for weighted graphs that relies only on parallel low-diameter decompositions and independent sampling. This yields the first algorithmic improvement over prior, solver-free parallel sparsification approaches since Koutis (2014) and, for the first time for a practical algorithm, eliminates any dependence on the target approximation accuracy $\epsilon$ in the algorithm's work and depth. Our algorithm works by sub-sampling edges according to their robust connectivity, as introduced by Kapralov and Panigrahy (2012). We show how to estimate the robust connectivities of $G$ in an extremely simple manner: we create multiple random sub graphs $G_p$, where each edge in $G$ is sub-sampled independently with probability $p_e = \min \{w_e \cdot p, 1\}$. Then, we run a Low Diameter Decomposition in each of the graphs. If $u$ and $v$ often share a cluster in the LDDs, then this provides us with an upper bound on the robust connectivity of the edge $e = (u,v)$. Carefully invoking this procedure for $O(\log n)$ different values of the probabilities $p$ then allows us to obtain sufficiently good estimates for sub-sampling. We additionally complement the theory with an experimental evaluation demonstrating strong performance across relevant graphs and sparsity regimes.

Figures

Figures reproduced from arXiv: 2607.25059 by the authors.

Figure 1
Figure 1. The number of PCG iterations as a function of the size of the graph. We first sparsify [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 2
Figure 2. The number of PCG iterations as a function of the sparsity of the graph. We first sparsify [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 5 linked inside Pith

  1. [3]

    A framework for parallelizing approximate gaussian elim- ination

    Yves Baumann and Rasmus Kyng. A framework for parallelizing approximate gaussian elim- ination. InProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Ar- chitectures, SPAA ’24, page 195–206, New York, NY, USA, 2024. Association for Computing Machinery.doi:10.1145/3626183.3659987

    arXiv 2024

  2. [8]

    Spectral sparsification via random spanners

    Michael Kapralov and Rina Panigrahy. Spectral sparsification via random spanners. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, page 393–398, New York, NY, USA, 2012. Association for Computing Machinery.doi: 10.1145/2090236.2090267

    arXiv 2012

  3. [1]

    Noah Amsel, Yves Baumann, Paul Beckman, Peter B¨ urgisser, Chris Cama˜ no, Tyler Chen, Ed- mond Chow, Anil Damle, Michal Derezinski, Mark Embree, Ethan N. Epperly, Robert Falgout, Mark Fornace, Anne Greenbaum, Chen Greif, Diana Halikias, Zhen Huang, Elias Jarlebring, Yiannis Koutis, Daniel Kressner, Rasmus Kyng, J¨ org Liesen, Jackie Lok, Raphael A. Meyer...

    arXiv 2026

  4. [2]

    Spielman, and Nikhil Srivastava

    Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers. SIAM Journal on Computing, 41(6):1704–1721, 2012.arXiv:https://doi.org/10.1137/ 090772873,doi:10.1137/090772873

    doi:10.1137/090772873 2012

  5. [4]

    Blelloch, and Julian Shun

    Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. Theoretically efficient parallel graph algorithms can be fast and scalable. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 293–304, 2018

    2018

  6. [5]

    Blelloch, and Julian Shun

    Laxman Dhulipala, Jessica Shi, Tom Tseng, Guy E. Blelloch, and Julian Shun. The graph based benchmark suite (GBBS). InInternational Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), pages 11:1–11:8, 2020

    2020

  7. [6]

    Dynamic low-stretch trees via dynamic low-diameter decompositions

    Sebastian Forster and Gramoz Goranci. Dynamic low-stretch trees via dynamic low-diameter decompositions. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 377–388, New York, NY, USA, 2019. Association for Computing Machinery.doi:10.1145/3313276.3316381

    arXiv 2019

  8. [7]

    Spielman

    Yuan Gao, Rasmus Kyng, and Daniel A. Spielman. Robust and practical solution of laplacian equations by approximate elimination, 2023. URL:https://arxiv.org/abs/2303.00709, arXiv:2303.00709

    arXiv 2023

Show all 23 references
  1. [9]

    Simple parallel and distributed algorithms for spectral graph sparsification,

    Ioannis Koutis. Simple parallel and distributed algorithms for spectral graph sparsification,

  2. [10]

    Faster spectral sparsification and numerical algorithms for sdd matrices, 2013

    Ioannis Koutis, Alex Levin, and Richard Peng. Faster spectral sparsification and numerical algorithms for sdd matrices, 2013. URL:https://arxiv.org/abs/1209.5821,arXiv:1209. 5821. 20

    2013 arXiv

  3. [11]

    Faster spectral sparsification and numerical algorithms for sdd matrices.ACM Trans

    Ioannis Koutis, Alex Levin, and Richard Peng. Faster spectral sparsification and numerical algorithms for sdd matrices.ACM Trans. Algorithms, 12(2), December 2015.doi:10.1145/ 2743021

    2015

  4. [12]

    Random-shift revisited: Tight approximations for tree embeddings andℓ 1-oblivious routings

    Rasmus Kyng, Maximilian Probst Gutenberg, and Tim Rieder. Random-shift revisited: Tight approximations for tree embeddings andℓ 1-oblivious routings. In2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2132–2142. IEEE, 2025

    2025

  5. [13]

    A framework for an- alyzing resparsification algorithms

    Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva. A framework for an- alyzing resparsification algorithms. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, page 2032–2043, USA, 2017. Society for In- dustrial and Appl...

  6. [14]

    Approximate gaussian elimination for laplacians: Fast, sparse, and simple, 2016

    Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians: Fast, sparse, and simple, 2016. URL:https://arxiv.org/abs/1605.02353,arXiv:1605.02353

    2016 arXiv

  7. [15]

    Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu

    Gary L. Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved parallel algorithms for spanners and hopsets. InProceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’15, page 192–201, New York, NY, USA, 2015. Association for Computi...

    2015

  8. [16]

    Miller, Richard Peng, and Shen Chen Xu

    Gary L. Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. InProceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algo- rithms and Architectures, SPAA ’13, page 196–203, New York, NY, USA, 2013. Association for Computin...

    2013

  9. [17]

    Probability and computing: Randomized algorithms and probabilistic analysis, 2005

    Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomized algorithms and probabilistic analysis, 2005

    2005

  10. [18]

    Society for Industrial and Ap- plied Mathematics, second edition, 2003

    Yousef Saad.Iterative Methods for Sparse Linear Systems. Society for Industrial and Ap- plied Mathematics, second edition, 2003. URL:https://epubs.siam.org/doi/abs/10.1137/ 1.9780898718003,arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9780898718003, doi:10.1137/1.9780898718003

    2003 doi

  11. [19]

    A simple and efficient parallel laplacian solver

    Sushant Sachdeva and Yibin Zhao. A simple and efficient parallel laplacian solver. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’23, page 315–325, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3558481.3591101

    2023

  12. [20]

    Spielman and Nikhil Srivastava

    Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913–1926, 2011.arXiv:https://doi.org/10.1137/ 080734029,doi:10.1137/080734029

    1913 doi

  13. [21]

    Spielman and Shang-Hua Teng

    Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, 2008. URL:https://arxiv.org/abs/cs/ 0310051,arXiv:cs/0310051

    2008 arXiv

  14. [22]

    Approximate distance oracles.J

    Mikkel Thorup and Uri Zwick. Approximate distance oracles.J. ACM, 52(1):1–24, January 2005.doi:10.1145/1044731.1044732. 21 Table 3: Condition numbers for the 2D dataset as a function of method andn. Entries are the median condition number over successful runs. Column abbreviat...

    2005

  15. [2014]

    URL:https://arxiv.org/abs/1402.3851,arXiv:1402.3851

    arXiv

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.