Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions

We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition, which is a decomposition of an unweighted graph into an edge-disjoint collection of sh...