TY - GEN

T1 - Fast and space efficient spectral sparsification in dynamic streams

AU - Kapralov, Michael

AU - Mousavifar, Aida

AU - Musco, Cameron

AU - Musco, Christopher

AU - Nouri, Navid

AU - Sidford, Aaron

AU - Tardos, Jakab

N1 - Funding Information:
This work was completed while Cameron Musco was employed at Microsoft Research New England. Michael Kapralov, Navid Nouri and Jakab Tardos are supported by ERC Starting Grant 759471. Aaron Sidford is supported by NSF CAREER Award CCF-1844855.
Funding Information:
Thiswork was completedwhileCameronMusco was emplo yed at Microsoft Researc h New England. Mic hael Kapralo v, Na vid Nouri and Jak ab Tardos are supported by ER C Starting Gran t 759471. AaronSidfordissupportedbyNSFCA-REER Aw ard CCF-1844855.

PY - 2020

Y1 - 2020

N2 - In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses Õ(n) space, and with high probability, recovers a spectral sparsifier from the sketch in Õ(n) time.1 Prior results either achieved near optimal Õ(n) space, but Ω(n2) recovery time [Kapralov et al. '14], or ran in o(n2) time, but used polynomially suboptimal space [Ahn et al '13]. Our main technical contribution is a novel method for recovering graph edges with high effective resistance from a linear sketch. We show how to do so in nearly linear time by 'bucketing' vertices of the input graph into clusters using a coarse approximation to the graph's effective resistance metric. A second main contribution is a new pseudorandom generator (PRG) for linear sketching algorithms. Constructed from a locally computable randomness extractor, our PRG stretches a seed of Õ(n) random bits polynomially in length with just logO(1) n runtime cost per evaluation. This improves on Nisan's commonly used PRG, which in our setting would require Õ(n) time per evaluation. Our faster PRG is essential to simultaneously achieving near optimal space and time complexity.

AB - In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses Õ(n) space, and with high probability, recovers a spectral sparsifier from the sketch in Õ(n) time.1 Prior results either achieved near optimal Õ(n) space, but Ω(n2) recovery time [Kapralov et al. '14], or ran in o(n2) time, but used polynomially suboptimal space [Ahn et al '13]. Our main technical contribution is a novel method for recovering graph edges with high effective resistance from a linear sketch. We show how to do so in nearly linear time by 'bucketing' vertices of the input graph into clusters using a coarse approximation to the graph's effective resistance metric. A second main contribution is a new pseudorandom generator (PRG) for linear sketching algorithms. Constructed from a locally computable randomness extractor, our PRG stretches a seed of Õ(n) random bits polynomially in length with just logO(1) n runtime cost per evaluation. This improves on Nisan's commonly used PRG, which in our setting would require Õ(n) time per evaluation. Our faster PRG is essential to simultaneously achieving near optimal space and time complexity.

UR - http://www.scopus.com/inward/record.url?scp=85084092034&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084092034&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85084092034

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1814

EP - 1833

BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

A2 - Chawla, Shuchi

PB - Association for Computing Machinery

T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

Y2 - 5 January 2020 through 8 January 2020

ER -