Theory Lunch Seminar

Wednesday, April 22, 2015 - 12:00pm to 1:00pm


8102 Gates & Hillman Centers


SARAH R. ALLEN, Ph.D. Student

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.

Event Website:

For More Information, Contact:


Seminar Series