Constructing Linear Sized Spectral Sparsification in Almost Linear Time
We present an almost linear time algorithm for constructing a spectral sparsifier with the number of edges linear in its number of vertices. This improves all previous constructions of linear sized spectral sparsifiers, which requires O(n2) time. A key ingredient in our algorithm is a novel combination of two techniques used in literature for constructing spectral sparsifiers: random sampling by effective resistance, and adaptive construction based on barrier functions.