REVIEW 1 cited by
Simple parallel and distributed algorithms for spectral graph sparsification
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
We describe a simple algorithm for spectral graph sparsification, based on iterative computations of weighted spanners and uniform sampling. Leveraging the algorithms of Baswana and Sen for computing spanners, we obtain the first distributed spectral sparsification algorithm. We also obtain a parallel algorithm with improved work and time guarantees. Combining this algorithm with the parallel framework of Peng and Spielman for solving symmetric diagonally dominant linear systems, we get a parallel solver which is much closer to being practical and significantly more efficient in terms of the total work.
Forward citations
Cited by 1 Pith paper
-
Parallel Spectral Graph Sparsification via Low Diameter Decompositions
Solver-free parallel spectral sparsification via LDD-based robust-connectivity estimates achieves O(m log n log nW) work and O(log² n log* n) depth with no ε factor in either resource.
Discussion (0). Continue with ORCID to comment.