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.
Publisher Copyright:
Copyright © 2020 by SIAM
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 -