Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee; He Sun

doi:/10.1137/16M1061850

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee, He Sun

Research output: Contribution to journal › Article › peer-review

Abstract / Description of output

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 Ω(n²) 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 language	English
Pages (from-to)	2315-2336
Number of pages	22
Journal	SIAM Journal on Computing
Volume	47
Issue number	6
Early online date	18 Dec 2018
DOIs	https://doi.org//10.1137/16M1061850
Publication status	E-pub ahead of print - 18 Dec 2018

Access to Document

/10.1137/16M1061850

Constructing Linear-Sized Spectral Sparsification in Almost-Linear TimeAccepted author manuscript, 383 KB

https://epubs.siam.org/doi/10.1137/16M1061850

1 Conference contribution

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
Lee, Y. T. & Sun, H., 2015, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. p. 250-269 20 p.
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cite this

@article{acf19e1c684c4820960b523a778e9b81,

title = "Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time",

abstract = "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.",

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

year = "2018",

month = dec,

day = "18",

doi = "/10.1137/16M1061850",

language = "English",

volume = "47",

pages = "2315--2336",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "6",

}

TY - JOUR

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

AU - Lee, Yin Tat

AU - Sun, He

PY - 2018/12/18

Y1 - 2018/12/18

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

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

U2 - /10.1137/16M1061850

DO - /10.1137/16M1061850

M3 - Article

SN - 0097-5397

VL - 47

SP - 2315

EP - 2336

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Abstract / Description of output

Access to Document

Fingerprint

Research output

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Cite this