Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee, He Sun

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present the first almost-linear time algorithm for constructing linear-sized spectral sparsification for graphs. This improves all previous constructions of linear-sized spectral sparsification, which requires Ω(n2) time [1], [2], [3]. A key ingredient in our algorithm is a novel combination of two techniques used in literature for constructing spectral sparsification: Random sampling by effective resistance [4], and adaptive constructions based on barrier functions [1], [3].
Original languageEnglish
Title of host publicationIEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015
Number of pages20
ISBN (Electronic)978-1-4673-8191-8
Publication statusPublished - 2015
EventFoundations of Computer Science 2015 - California, Berkley, United States
Duration: 17 Oct 201520 Oct 2015


ConferenceFoundations of Computer Science 2015
Country/TerritoryUnited States
Internet address


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

Cite this