Sparsifying Cayley Graphs on Every Group

Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty +2

A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a $(1\pm \epsilon )$ cut (or spectral) sparsifier which prese…