Deterministic Spectral Sparsification in Almost-Linear Time for Dense Graphs

Jason Li, Trevor Vaughn

A spectral sparsifier of a weighted graph is a reweighted subgraph whose Laplacian quadratic form approximates that of the original graph. Let $G$ be a positively weighted $n$-vert…