# Analysis of Kelner and Levin graph sparsification algorithm for a streaming setting

arXiv: https://arxiv.org/abs/1609.03769 · HTML: https://mlsanity.com/paper/1609.03769/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Sep 2016.

## Built on by (most cited first, 1 of 1)

- [Improved large-scale graph learning through ridge spectral sparsification](https://mlsanity.com/paper/2604.20078/) (2026)

## Abstract (arXiv)

We derive a new proof to show that the incremental resparsification algorithm proposed by Kelner and Levin (2013) produces a spectral sparsifier in high probability. We rigorously take into account the dependencies across subsequent resparsifications using martingale inequalities, fixing a flaw in the original analysis.