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

09/13/2016

∙

by   Daniele Calandriello, et al.

∙

0

∙

share

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.