Noise Sensitivity Lecture and Tales

 

A lecture about Noise sensitivity

Several of my recent research projects are related to noise, and noise was also a topic of a recent somewhat philosophical post.   My oldest and perhaps most respectable noise-related project was the work with Itai Benjamini and Oded Schramm on noise sensitivity of Boolean functions. Recently I gave lectures at several places about noise sensitivity and noise stability of Boolean functions, starting with the definition of these terms and their Fourier description,  then the result of Itai, Oded and myself that the crossing event of planar critical percolation is noise-sensitive, and ending with two recent breakthrough results. One is the work by Garban, Pete, and Schramm   that described the scaling limit of the spectral distribution for the crossing event in critical percolation. The second is  the “majority is stablest” theorem of Mossel, O’Donnell, and Oleszkiewicz and the connections to hardness of approximation.

A fun way to explain noise sensitivity (especially after the 2000 US election) is in terms of the probability that small mistakes in counting the votes in an election will change the outcome. Here we assume that there are two candidates, that every voter votes with probability 1/2 for each candidate (independently) and that when we count every ballot there is a small probability t that the voter intention is reversed.

Noise sensitivity is one of the reasons to reject the HEX voting rule; but perhaps not the main one :) . (Noise stability/sensitivity and the related notion of influence play some role in the recent polymath1 project.)

Here is the power point presentation. I hope to blog at a later time about analysis of Boolean functions and about noise sensitivity and noise stability. 

Meanwhile let me just give a few general comments and tales: 

Some noise sensitivity tales:

1. We started working on noise sensitivity in 1995 and at that time Itai was expecting a son, so a friend lent him a pager. When we wrote the paper Alon was already 4 years old.

bks

2. The paper by Boris Tsirelson and Anatoly Vershik (that also describes work spanning many years) contains a similar notion. Their motivation was entirely different.  One difficulty in translating the two formulations is that “Boolean function” (or rather “a sequence of Boolean functions + some uniformity condition” ) in our work  is translated to “noise” in Tsirelson’s terminology. And “noise sensitive” is translated to “black” or “non-Fock” or “non-classical” in their work. 

3. After the 2000 elections Itai Benjamini and Elchanan Mossel wrote a popular piece about the relevance of this work for elections. Mathematician and writer Barry Cipra wrote a lovely  small article about it. (Looking at it now I find it very impressive how Barry put so much information in a vivid way in such a short article.)

Here is one paragraph from Cipra’s article:

“Three researchers—Itai Benjamini and Oded Schramm, both of Microsoft Research, and Gil Kalai of the Hebrew University in Jerusalem—have turned the question around: How close does a race have to be in order for errors in counting to have a non-negligible chance of reversing the outcome? Their analysis indicates that a simple, nationwide popular vote would be more stable against mistakes than the beleaguered Electoral College system. Indeed, they find, straightforward majority vote is more stable than any other voting method.”

At that time we had a long email discussion between Itai, Oded, Elchanan, Yuval Peres, Russ Lyons and me about the interpretation of the notions and theorems. For example, does the fact that majority is more noise-stable than 2-level majority means that what happened in the 2000 US elections are more likely to occur in the US system than in a country with a popular vote?  Russ Lyons was especially skeptical about the relevance of our notions and results to real-life elections.

In these discussions we somehow took for granted that majority is the most noise-stable voting method (under some symmetry assumption) as we earlier told Barry. Only several months into the discussion did we realize that this is not a theorem and we do not know how to prove it. Is it true? Yes! This is the 2005 result of Mossel, O’Donnell, and Oleszkiewicz (which had an entirely different motivation). Are these results relevant to real-life elections? I think to some extent they are. In 2007 I wrote a paper about noise sensitivity and noise stability in the context of social choice theory.

4. Some years after the first paper Itai, Oded, and I  had ideas about how to use noise sensitivity to give better upper bounds on the fluctuations of “first passage percolation”. We first had a complicated connection between noise sensitivity and variance computations that improved the known O(n) upper bounds to o(n); then we spent a summer at Microsoft improving the bounds to O(n/\sqrt{\log n}) which was even more complicated; and finally we found a simple argument giving O(n/\log n) which made the difficult efforts obsolete. Together and separately we tried to use the stability/sensitivity dichotomy in several other directions.

5. A couple of years ago I had some wild thoughts about the usefulness of noise sensitivity in physics, which turned out to be somewhat related to Tsirelson and Vershik’s original motivation. Very roughly the idea is that (quantum) stochastic processes that we can measure or experiment are necessarily noise-stable, and that current high-energy physics models describe noise-stable stochastic distributions.  (Or are ambiguous about the noise sensitivity issue.) A brief account of the idea is presented in this paper, and (with more details) in the following power point lecture that I gave at the HU hep-seminar. (It has the same first half as the presentation above.). Itai and Oded were quite (positively) amused by these ideas.

Related Presentations

A related presentation by Ryan O’Donnell

Stability and chaos in boolean functions (pps)
     

A related presentation by Oded Schramm

And here is a great presentation of Oded Schramm about his work with Garban and Peter, earlier work with Steiff and some basic things about noise sensitivity.

The Percolation Fourier Spectrum (2007)

         Abstract: A real valued function f on the discrete cube \{-1,1\}^n has an expansion of the form f(x)=\sum_S F(S) u_S(x), where u_S(x) = \prod_{j\in S} x_j, and the sum is over all subsets S of the index set [n]. When f takes values in {-1,1}, the measure on such S given by \mu(S)=F(S)^2 is a probability measure. The distribution of |S| under this measure encodes important aspects of the behaviour of f under noise and under the natural dynamics on the discrete cube. In joint work with Christophe Garban and Gabor Pete we describe \mu in the case where f = 1 or -1, depending on whether there is a percolation crossing or not. We derive consequences for the behavior of percolation under noise and for exceptional times of dynamical percolation. Background in percolation theory will not be assumed.
About these ads
This entry was posted in Combinatorics, Computer Science and Optimization, Probability and tagged , , , , , , . Bookmark the permalink.

12 Responses to Noise Sensitivity Lecture and Tales

  1. Gil Kalai says:

    Let me also mention a recent important paper by Sourav Chatterjee

    http://front.math.ucdavis.edu/0810.4221

    entitled “Chaos, concentration, and multiple valleys” which among many other things bring the noise sensitivity story to various unexpected places (and also gives a whole new way to look at first passage percoation).

  2. Dear Gil Kalai,

    just to point out that we used very much the paper by Mossel, O’Donnell, and Oleszkiewicz (that you mention in your post) in our recent work

    http://arxiv.org/abs/0904.1153

    where we deduced universality results for homogenous sums in general random variables, by using exactly the notion of ” influence” + many other probabilistic techniques.

    Best

    Giovanni Peccati

  3. gil.kalai says:

    Dear Giovanni

    Thanks a lot! Gil

  4. Gil Kalai says:

    A nice blog description of the invariance principle of Mossel, O’Donnell, and Oleszkiewicz which is part of their proof for majority is stablest theorem can be found here:

    http://tcsmath.wordpress.com/2009/06/19/lecture-p1-from-integrality-gaps-to-dictatorship-tests/

  5. Dear Gil,
    thank for this new link!
    Best
    Giovanni

  6. Giovanni Peccati says:

    Dear Gil,

    there is a new paper based on CLTs stemming from the MOO invariance principle (here is the link)

    http://arxiv.org/abs/0908.0391

    Here, we establish universal Gaussian fluctuations for traces of general (possibly discrete, as Bernoulli) matrix ensembles.

    All the best

    Giovanni

  7. Gil Kalai says:

    Thanks again Giovanni, please keep us posted!

  8. Pingback: Noise Stability and Threshold Circuits « Combinatorics and more

  9. Pingback: Analysis of Boolean Functions | Combinatorics and more

  10. Pingback: The Hex-Voting-Rule (Not Recommended) | Combinatorics and more

  11. Pingback: Noise Sensitivity and Percolation. Lecture Notes by Christophe Garban and Jeff Steif | Combinatorics and more

  12. Pingback: BosonSampling and (BKS) Noise Sensitivity | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s