A Sketching Algorithm for Spectral Graph Sparsification

Jiecao Chen, Bo Qin, David P. Woodruff +1

We study the problem of compressing a weighted graph $G$ on $n$ vertices, building a "sketch" $H$ of $G$, so that given any vector $x\in {\mathbb{R}}^n$, the value $x^T{L}_{G}x$ can b…