### 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 Ω(n^{2}) recovery time [Kapralov et al. '14], or ran in o(n^{2}) 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 log^{O}^{(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 language | English (US) |
---|---|

Title of host publication | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 |

Editors | Shuchi Chawla |

Publisher | Association for Computing Machinery |

Pages | 1814-1833 |

Number of pages | 20 |

ISBN (Electronic) | 9781611975994 |

State | Published - 2020 |

Event | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States Duration: Jan 5 2020 → Jan 8 2020 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 2020-January |

### Conference

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

Country | United States |

City | Salt Lake City |

Period | 1/5/20 → 1/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

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