mlsanityData to 7 Oct 2026

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

arXiv 1508.03261 ↗First posted 13 Aug 2015cs.DS cs.DMcited by 17

Not on the map. Why?

Abstract (arXiv)

We present the first almost-linear time algorithm for constructing linear-sized spectral sparsification for graphs. This improves all previous constructions of linear-sized spectral sparsification, which requires Omega(n2) time. A key ingredient in our algorithm is a novel combination of two techniques used in literature for constructing spectral sparsification: Random sampling by effective resistance, and adaptive constructions based on barrier functions.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 Aug 2015.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 3; 2023: 3; 2024: 5; 2025: 3.

17 papers.

Sort:

  1. 2024A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensationcited by 57
  2. 2021Graph Coarsening with Neural Networkscited by 55
  3. 2024Graph Coarsening with Message-Passing Guaranteescited by 9
  4. 2021A Generic Graph Sparsification Framework using Deep Reinforcement Learningcited by 8
  5. 2024Optimal sampling for least-squares approximationcited by 6
  6. 2025Large-Scale Spectral Graph Neural Networks via Laplacian Sparsification: Technical Reportcited by 5
  7. 2023Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basiscited by 4
  8. 2022Sparsification of Decomposable Submodular Functionscited by 3
  9. 2023Fast Approximation of Similarity Graphs with Kernel Density Estimationcited by 3
  10. 2024Robust Offline Active Learning on Graphscited by 3
  11. 2025Taxonomy of reduction matrices for Graph Coarseningcited by 3
  12. 2022Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimationcited by 2
5 more
  1. 2022Sparsification of the regularized magnetic Laplacian with multi-type spanning forestscited by 1
  2. 2021Semi-supervised Active Regressioncited by 0
  3. 2023PRIMO: Private Regression in Multiple Outcomescited by 0
  4. 2024Almost linear time differentially private release of synthetic graphscited by 0
  5. 2025Online Sparsification of Bipartite-Like Clusters in Graphscited by 0