Given a joint distribution of Boolean variables, we consider conditioning on a random subset of these variables in order to reduce the expected covariance between an average pair of the remaining variables. This problem arises in the context of global correlation rounding for convex relaxation hierarchies. We conjecture that is sufficient to condition on O(1/eps) variables to achieve an average covariance of at most epsilon in expectation and we prove the conjecture in the case where the variables are the leaves of an information flow tree whose underlying graph is a caterpillar graph (similar to a two-state hidden Markov model).

This is joint work with Ryan O'Donnell.