Title:Guassian tools in hardness of approximation, social choice and combinatorics
Speaker: Elchanan Mossel UC Berkeley
Time: 2007-11-09 16:00-2007-11-09 17:00
Venue:FIT Building 4-603, Tsinghua University
Download:Click!

Abstract:

      I will review some applications of a new probabilistic invariance principle 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. The invariance principle is also applicable in the theory of social choice and allows to devise a new approach to study problems in additive combinatorics.
      Partially based on joint works with Austrin,Dinur,Khot,Kindler,O'Donnell, Oleszkiewicz' and Regev.



Short Bio:

    Prof. Elchanan Mossel studies mathematical and algorithmic problems arising in the theory of computing, as well as in such areas as molecular biology, evolution and social choice. He is particularly interested in problems of combinatorial and and probabilistic flavor and in large-scale analysis.      Born in Jerusalem in 1973, he received a B.Sc. magna cum laude in mathematics and natural sciences from the Open University of Israel in 1992. He conducted his graduate studies in mathematics at the Hebrew University of Jerusalem, earning an M.Sc. magna cum laude in 1997 and a Ph.D. in 2000. After conducting postdoctoral studies in the theory group of Microsoft's research division for two years, he moved to the University of California at Berkeley in 2002, first as a postdoctoral fellow and then as an assistant and an associate professor. He has received a number of grants and awards, including an Alfred Sloan Fellowship in mathematics, a Miller Fellowship and a National Science Foundation Career Award.