Fast and space efficient spectral sparsification in dynamic streams

Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, Jakab Tardos

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
    EditorsShuchi Chawla
    PublisherAssociation for Computing Machinery
    Pages1814-1833
    Number of pages20
    ISBN (Electronic)9781611975994
    StatePublished - 2020
    Event31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States
    Duration: Jan 5 2020Jan 8 2020

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
    Volume2020-January

    Conference

    Conference31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
    CountryUnited States
    CitySalt Lake City
    Period1/5/201/8/20

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Fast and space efficient spectral sparsification in dynamic streams'. Together they form a unique fingerprint.

  • Cite this

    Kapralov, M., Mousavifar, A., Musco, C., Musco, C., Nouri, N., Sidford, A., & Tardos, J. (2020). Fast and space efficient spectral sparsification in dynamic streams. In S. Chawla (Ed.), 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 (pp. 1814-1833). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2020-January). Association for Computing Machinery.