| Monday, January 20th, 2014 | 4pm-5pm | Burnside 1205 |
Negative dependence is a useful property of random variables, and one that is often exploited in algorithms based on dependent random sampling. But it does not seem to always be enough. In particular, while concentration results are known for sums of negatively dependent scalar-valued random variables, as well as sums of independent matrix-valued random variables, they are not known for sums of negatively dependent matrices. We show how this obstacle can be bypassed for pipage rounding, an important and popular dependent rounding technique. Using a method we call "concavity of pessimistic estimators", we show concentration of submodular functions and concentration of matrix sums under pipage rounding. To prove the latter result, we derive a new variant of Lieb's celebrated concavity theorem in matrix analysis. One main application of these results is to "spectrally-thin trees", a spectral analog of the thin trees that played a crucial role in the recent breakthrough on the asymmetric travelling salesman problem. (Joint work with Nick Harvey)