Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee, He Sun

Research output: Contribution to journalArticlepeer-review


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 Ω(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.
Original languageEnglish
Pages (from-to)2315-2336
Number of pages22
JournalSIAM Journal on Computing
Issue number6
Early online date18 Dec 2018
Publication statusE-pub ahead of print - 18 Dec 2018


Dive into the research topics of 'Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time'. Together they form a unique fingerprint.

Cite this