Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates

Zeyuan Allen-Zhu, Zhenyu Liao, Lorenzo Orecchia

In this paper, we provide a novel construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava [BSS14]. While previous constructions required $\Omega (n^4)$ r…