Spectral Sparsification of Graphs

Daniel A. Spielman, Shang‐Hua Teng

Type: Preprint

Publication Date: 2008-01-01

Citations: 19

DOI: https://doi.org/10.48550/arxiv.0808.4134

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Spectral Sparsification of Graphs	2011	Daniel A. Spielman Shang‐Hua Teng
+ PDF Chat	Spectral sparsification of graphs	2013	Joshua Batson Daniel A. Spielman Nikhil Srivastava Shang‐Hua Teng
+ PDF Chat	Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices	2015	Ioannis Koutis A. Levin Richard Peng
+	Faster spectral sparsification and numerical algorithms for SDD matrices	2012	Ioannis Koutis A. Levin Richard Peng
+	Spectral Hypergraph Sparsifiers of Nearly Linear Size.	2021	Michael Kapralov Robert Krauthgamer Jakab Tardos Yuichi Yoshida
+	Spectral Hypergraph Sparsifiers of Nearly Linear Size	2021	Michael Kapralov Robert Krauthgamer Jakab Tardos Yuichi Yoshida
+	An Efficient Algorithm for Unweighted Spectral Graph Sparsification	2014	David G. Anderson Ming Gu Christopher Melgaard
+	Towards Scalable Spectral Sparsification of Directed Graphs	2019	Ying Zhang Zhiqiang Zhao Zhuo Feng
+	Subgraph Sparsification and Nearly Optimal Ultrasparsifiers	2009	Alexandra Kolla Yury Makarychev Amin Saberi Shang‐Hua Teng
+ PDF Chat	Graph Sparsification by Approximate matrix Multiplication	2023	Neophytos Charalambides Alfred O. Hero
+ PDF Chat	Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems	2004	Daniel A. Spielman Shang‐Hua Teng
+ PDF Chat	Twice-Ramanujan Sparsifiers	2014	Joshua Batson Daniel A. Spielman Nikhil Srivastava
+	An SDP-Based Algorithm for Linear-Sized Spectral Sparsification	2017	Yin Tat Lee He Sun
+	Spectral sparsification and restricted invertibility	2010	Daniel A. Spielman Nikhil Srivastava
+	Spectral Subspace Sparsification	2018	Huan Li Aaron Schild
+ PDF Chat	Spectral Subspace Sparsification	2018	Huan Li Aaron Schild
+	Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving	2019	Simon Apers Ronald de Wolf
+ PDF Chat	Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	2022	Simon Apers Ronald de Wolf
+	Spectral graph sparsification in nearly-linear time leveraging efficient spectral perturbation analysis	2016	Zhuo Feng
+ PDF Chat	Spectral Hypergraph Sparsifiers of Nearly Linear Size	2022	Michael Kapralov Robert Krauthgamer Jakab Tardos Yuichi Yoshida

Works That Cite This (15)

Action	Title	Year	Authors
+	The Laplacian Paradigm: Emerging Algorithms for Massive Graphs	2010	Shang‐Hua Teng
+	Numerical Thinking in Algorithm Design and Analysis	2011	Shang‐Hua Teng
+	The work of Daniel A. Spielman	2011	Gil Kalai
+	Approximate Inverse Chain Preconditioner: Iteration Count Case Study for Spectral Support Solvers	2020	M. Harper Langston Pierre-David Létourneau Julia Wei Larry Weintraub Mitchell Harris Richard Lethin Eric Papenhausen Meifeng Lin
+	Finite Volume Spaces and Sparsification	2010	Ilan Newman Yuri Rabinovich
+	LSP : Acceleration and Regularization of Graph Neural Networks via Locality Sensitive Pruning of Graphs	2021	Eitan Kosman Joel Oren Dotan Di Castro
+ PDF Chat	An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations	2013	Jonathan A. Kelner Yin Tat Lee Lorenzo Orecchia Aaron Sidford
+ PDF Chat	Information Graph Flow: A Geometric Approximation of Quantum and Statistical Systems	2018	Vitaly Vanchurin
+ PDF Chat	Semisupervised Manifold Alignment of Multimodal Remote Sensing Images	2014	Devis Tuia Michele Volpi Maxime Trolliet Gustau Camps‐Valls
+	Accurately Modeling Biased Random Walks on Weighted Graphs Using Node2vec	2021	Renming Liu Matthew Hirn Arjun Krishnan

Works Cited by This (15)

Action	Title	Year	Authors
+	Spectral Graph Theory	1996	Fan Chung
+	Fast computation of low-rank matrix approximations	2007	Dimitris Achlioptas Frank McSherry
+	Probabilistic construction of deterministic algorithms: Approximating packing integer programs	1986	Prabhakar Raghavan
+ PDF Chat	Geometric Bounds for Eigenvalues of Markov Chains	1991	Persi Diaconis Daniel W. Stroock
+ PDF Chat	Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems	2004	Daniel A. Spielman Shang‐Hua Teng
+ PDF Chat	Approximate counting, uniform generation and rapidly mixing Markov chains	1989	Alistair Sinclair Mark Jerrum
+	The eigenvalues of random symmetric matrices	1981	Zoltán Füredi János Komlós
+	THE LAPLACIAN SPECTRUM OF GRAPHS y	1991	Bojan Mohar
+ PDF Chat	Twice-ramanujan sparsifiers	2009	Joshua Batson Daniel A. Spielman Nikhil Srivastava
+	Spectral norm of random matrices	2007	Van H. Vu