The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP

Understand

Marcus, Spielman, and Srivastava in their seminal work \cite{MSS13} resolved the Kadison-Singer conjecture by proving that for any set of finitely supported independently distributed random vectors $v_1,\dots, v_n$ which have "small" expected squared norm and are in isotropic position (in expectation), there is a positive probability that the sum $\sum v_i v_i^\intercal$ has small spectral norm.

• Their proof crucially employs real stability of polynomials which is the natural generalization of real-rootedness to multivariate polynomials.
• Strongly Rayleigh distributions are families of probability distributions whose generating polynomials are real stable \cite{BBL09}.
• As independent distributions are just special cases of strongly Rayleigh measures, it is a natural question to see if the main theorem of \cite{MSS13} can be extended to families of vectors assigned to the elements of a strongly Rayleigh distribution.