Thursday, 18th January 2007, 4:00 pm
Mathematics Building, Lecture Hall 2
Elchanan Mossel
(University of California at Berkeley)
"A nonlinear invariance principle with applications"
Abstract:
I will discuss some recent results answering questions like:
The probability of an Arrow paradox: What is the social choice function
that minimizes the probability of a "paradox"?
"It ain't over until it's over": What is the social choice function that
maximizes the prediction probability from a random sample?
What is the best approximation algorithm for finding the maximum cut in a
graph?
What is the minimal number of colors for which one can efficiently color
a 4 colorable graph?
Interestingly, the analysis of these problems relies on a non-linear
invariance principle and on isoperimetric analysis of the
Orenstein-Uhlenbeck process. Based on on joint works with:
Khot, Kindler and O'Donnell; O'Donnell and Oleszkiewics; and Dinur and Regev
Light refreshments will be served in the faculty lounge at 3:30.
