Computational Hardness via Gaussian Isoperimetric Inequalities



Elchanan Mossel

Assistant Professor of Statistics at UC Berkeley

Monday  Sept. 12, 2006
4:00 PM, 406 Malott


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.