# Mittag-Leffler Institute and Yale, Winter 2005; Test your intuition: Who Played the Piano?

This is a little “flashback” intermission in my posts about my debate with Aram Harrow. This time I try to refer to Cris Moore’s question regarding  the motivation for my study. For the readers it gives an opportunity to win a \$50 prize!

Let me also bring to your attention an interesting discussion (starting here) between Peter Shor and me regarding smoothed Lindblad evolutions.

(Cris Moore, the debate’s very first comment!) I am also a little confused by Gil’s motivation for his conjectures.  (My response:)  To the best of my memory, my main motivation for skeptically studying quantum fault-tolerance was that I thought that this is a direction worth pursuing and that I had a shot at it.

While listening with Ravi Kannan to this 2002 lecture by Michel Devoret at Yale, I wondered if there are enough scientists working on the “mirage” side.

# Flashback: Mittag-Leffler 2005

I started systematically thinking about quantum fault-tolerance in February 2005. There were several things that triggered my interest to the question in the previous fall and I decided to spend some time learning and thinking about it in our winter break.  One of those triggers was something Dorit Aharonov told me a few months earlier: she said that once, when she was telling her students about quantum computers, she suddenly had a feeling that maybe it was all just nonsense. Another trigger came from a former student who told me about a Polish scientist (whose name he could not remember) who wrote an article about impossibility of quantum error-correction. I thought that the lack of a quantum analog of the repetition code, and the unique properties of the majority function  in terms of sensitivity to noise that I studied with Itai Benjamini and Oded Schramm earlier could be a good starting point for looking skeptically at quantum computers.

In our 2005 winter break, I spent two weeks at Yale and then additional two weeks at the Mittag-Leffler institute near Stockholm.  At Yale, I only had little time to think about quantum computers. I had to finish a survey article with Muli Safra about threshold phenomena (To a volume that Cris Moore and Allon Perkus were among the editors).  One of the last days in Yale we went to dinner with two guests, Chris Skinner who gave the colloquium talk, and Andrei Okounkov who visited me and gave a talk about partition enumeration and mirror symmetry. At the dinner Andrew Casson asked, out of the blue, if we think that quantum computers can be built and it almost seemed as if that Andrew was reading my mind on what I plan to work on the weeks to come. My answer there was the same as my answer now, that I tend to find it implausible.

Mittag-Leffler Institute February 2005 with Xavier Viennot and Alain Lascoux

In Sweden I spent most of my time on quantum fault-tolerance. I was jet-lagged and being jet-lagged in the Mittag-Leffler institute already worked for me once, when finding my subexponential randomized variant of the simplex algorithm was a substitute for sleeping some night in fall 1991 . In 2005 it was not as bad, I just came to my office very early in the morning and started working. And very early in the morning somebody was already playing the piano.

And who was playing the piano at the institute in the cold Swedish mornings of February 2005? The first reader to guess correctly, and convince me in a comment that she or he knows the answer without revealing it to everybody else will get \$50. Continue reading

# Midrasha Talks are Now Online

Itai Benjamini listening to Gadi Kozma

There are 41 lectures from the Midrasha on Probability and Geometry: The Mathematics of Oded Schramm which are now online.

Joram Lindenstrauss’s concluding lecture (click on the picture to see)

Laci Lovasz

More pictures and links to some lectures below the line (I will slowly update them).

# Midrasha News

Our Midrasha is going very very well. There are many great talks, mostly very clear and helpful. Various different directions which interlace very nicely. Some moving new mathematical breakthroughs; very few fresh from the oven. Tomorrow is the last day.

Update: I will try to describe some highlights an links to the presentations, related papers, and pictures at a later post.

# A Conference and a School on Oded Schramm’s Mathematics

There will be a conference this summer in Redmond and a school in December in Jerusalem devoted to Oded Schramm’s mathematics.

## Redmond WA, August 30-31, 2009

To be held at Microsoft Research.

Here are links to the conference page and conference poster

Speakers include

 Omer Angel (University of British Columbia) Itai Benjamini (Weizmann Institute) Mario Bonk (University of Michigan) Michael Freedman (Microsoft Station Q) Christophe Garban (ֹcole Normale Supיrieure) Olle Haggstrom (Chalmers University of Technology) Zheng-Xu He (Beijing CAS Institute of Mathematics) Gregory F. Lawler (University of Chicago) Russell Lyons (Indiana University) Assaf Naor (New York University) Yuval Peres (Microsoft Research) Gabor Pete (University of Toronto) Steffen Rohde (University of Washington) Scott Sheffield (Massachusetts Institute of Technology) Stanislav Smirnov (Universitי de Genטve) Wendelin Werner (Universitי Paris-Sud XI) David B. Wilson (Microsoft Research)

## Jerusalem, 15-23 December 2009

To be held at the Hebrew University of Jerusalem, the Institute for Advanced Study, Feldman Building Givat Ram Campus. Continue reading

# 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.

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.” Continue reading

# Oded

I just heard the terrible news that Oded Schramm was killed in a hiking accident. Oded was hiking on Guye Peak near Snoqualmie Pass near Seattle. This is a terrible loss to Oded’s family, and our hearts and thoughts are with his wife Avivit and children Tselil and Pele. This is a great personal loss to me, to his many friends, and to mathematics.