Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee; He Sun

doi:10.1109/FOCS.2015.24

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee, He Sun

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

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²) 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 language	English
Title of host publication	IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015
Pages	250-269
Number of pages	20
ISBN (Electronic)	978-1-4673-8191-8
DOIs	https://doi.org/10.1109/FOCS.2015.24
Publication status	Published - 2015
Event	Foundations of Computer Science 2015 - California, Berkley, United States Duration: 17 Oct 2015 → 20 Oct 2015 http://ieee-focs.org/

Conference

Conference	Foundations of Computer Science 2015
Country/Territory	United States
City	Berkley
Period	17/10/15 → 20/10/15
Internet address	http://ieee-focs.org/

Access to Document

10.1109/FOCS.2015.24

http://ieeexplore.ieee.org/document/7354398/

1 Article

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
Lee, Y. T. & Sun, H., 18 Dec 2018, (E-pub ahead of print) In: SIAM Journal on Computing. 47, 6, p. 2315-2336 22 p.
Research output: Contribution to journal › Article › peer-review

Open Access
File

He Sun
Person: Academic: Research Active (Teaching)

Cite this

@inproceedings{6073f9d459614aa6bcae077d63f7b491,

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 Ω(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].",

author = "Lee, {Yin Tat} and He Sun",

year = "2015",

doi = "10.1109/FOCS.2015.24",

language = "English",

pages = "250--269",

booktitle = "IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015",

note = "Foundations of Computer Science 2015 ; Conference date: 17-10-2015 Through 20-10-2015",

url = "http://ieee-focs.org/",

}

TY - GEN

T1 - Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

AU - Lee, Yin Tat

AU - Sun, He

PY - 2015

Y1 - 2015

N2 - 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].

AB - 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].

U2 - 10.1109/FOCS.2015.24

DO - 10.1109/FOCS.2015.24

M3 - Conference contribution

SP - 250

EP - 269

BT - IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015

T2 - Foundations of Computer Science 2015

Y2 - 17 October 2015 through 20 October 2015

ER -

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Abstract / Description of output

Conference

Access to Document

Fingerprint

Research output

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Profiles

He Sun

Cite this