A Framework for Analyzing Resparsification Algorithms

Rasmus Kyng, Jakub Pachocki, Richard Peng +1

A spectral sparsifier of a graph $G$ is a sparser graph $H$ that approximately preserves the quadratic form of $G$, i.e. for all vectors $x$, $x^T{L}_{G}x\approx x^T{L}_{H}x$, where $…