Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems

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

Daniel A. Spielman , Shang-Hua Teng This is my paper · ORCID

classification cs.DScs.NAmath.NA

keywords arxivgraphalgorithmsbeendividedlinearnearly-linearpartitioning

verification ladder T0 review T1 audit T2 compute T3 formal

No signed human review yet.

0 comments

read the original abstract

This paper has been divided into three papers. arXiv:0809.3232, arXiv:0808.4134, arXiv:cs/0607105

Forward citations

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Parallel Spectral Graph Sparsification via Low Diameter Decompositions
cs.DS 2026-07 conditional novelty 7.0 of 10

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.