A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees

Rasmus Kyng, Zhao Song

Strongly Rayleigh distributions are a class of negatively dependent distributions of binary-valued random variables [Borcea, Branden, Liggett JAMS 09]. Recently, these distribution…