Jerusalem Mathematics Colloquium

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:

  1. The probability of an Arrow paradox: What is the social choice function that minimizes the probability of a "paradox"?
  2. "It ain't over until it's over": What is the social choice function that maximizes the prediction probability from a random sample?
  3. What is the best approximation algorithm for finding the maximum cut in a graph?
  4. 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.

List of talks, 2006-07
Archive of talks