Computational Hardness via Gaussian Isoperimetric Inequalities
Elchanan Mossel
Assistant Professor of Statistics at UC Berkeley
Abstract: In this talk I will review some applications of a new probabilistic invariance principle derived jointly with R. O'Donnell and K. Oleszkiewicz for functions that are stable against noise acting independently on each coordinate in a product space. This invariance principle in conjunction with a strong "hardness of approximation" paradigm developed by Khot allows to obtain several new/tight hardness of approximation results for graph problems such are MAX-CUT and graph coloring.