Fall 2013

Generalizations of the KKL Theorem and Friedgut's Junta Theorem

Tuesday, Aug. 27, 2013 11:30 am11:55 am

Add to Calendar

We will survey various generalizations of the results of Kahn, Kalai, and Linial, and that of Friedgut (Friedgut's Junta theorem) to graphs other than the hypercube. Of particular interest will be their generalization to the setting of Cartesian product of arbitrary undirected graphs (or equivalently, reversible Markov chains) because of their applications to hardness of approximation. We will sketch a proof in this setting, extending the arguments of Rossignol, and Falik-Samorodnitsky.

This is joint work with Madhur Tulsiani.