@inproceedings{08bc09099414434ca0c39ce0427901ec,
title = "Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time",
abstract = "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 Ω(n 2 ) 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].",
author = "He Sun and Lee, {Yin Tat}",
year = "2015",
month = oct,
day = "17",
doi = "10.1109/FOCS.2015.24",
language = "English",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",
pages = "250--269",
booktitle = "2015 IEEE 56th Annual Symposium on Foundations of Computer Science",
address = "United States",
}