# Influence, Threshold, and Noise

My dear friend Itai Benjamini told me that he won’t be able to make it to my Tuesday talk on influence, threshold, and noise, and asked if I already have  the slides. So it occurred to me that perhaps I can practice the lecture on you, my readers, not just with the slides (here they are) but also roughly what I plan to say, some additional info, and some pedagogical hesitations. Of course, remarks can be very helpful.

I can also briefly report that there are plenty of exciting things happening around that I would love to report about – hopefully later in my travel-free summer. One more thing: while chatting with Yuval Rabani and Daniel Spielman I realized that there are various exciting things happening in algorithms (and not reported so much in blogs). Much progress has been made on basic questions: TSP, Bin Packing, flows & bipartite matching, market equilibria, and k-servers, to mention a few, and also new directions and methods. I am happy to announce that Yuval kindly agreed to write here an algorithmic column from time to time, and Daniel is considering contributing a guest post as well.

## The second AMS-IMU meeting

Since the early 70s, I have been a devoted participants in our annual meetings of the Israeli Mathematical Union (IMU), and this year we will have the second joint meeting with the American Mathematical Society (AMS). Here is the program. There are many exciting lectures. Let me mention that Eran Nevo, this year Erdős’ prize winner, will give a lecture about the g-conjecture. Congratulations, Eran! Among the 22 exciting special sessions there are a few related to combinatorics, and even one organized by me on Wednsday and Thursday.

 Combinatorics Contact person: Gil Kalai, gil.kalai@gmail.com TAU, Dan David building, Room 103 Wed, 10:50-11:30 Van H. Vu (Yale University) Real roots of random polynomials (abstract) Wed, 11:40-12:20 Oriol Serra (Universitat Politecnica de Catalunya, Barcelona) Arithmetic Removal Lemmas (abstract) Wed, 12:30-13:10 Tali Kaufman (Bar-Ilan University) Bounded degree high dimensional expanders (abstract) Wed, 16:00-16:40 Rom Pinchasi (Technion) On the union of arithmetic progressions (abstract) Wed, 16:50-17:30 Isabella Novik (University of Washington, Seattle) Face numbers of balanced spheres, manifolds, and pseudomanifolds (abstract) Wed, 17:40-18:20 Edward Scheinerman (Johns Hopkins University, Baltimore) On Vertex, Edge, and Vertex-Edge Random Graphs (abstract) Thu, 9:20-10:00 Yael Tauman Kalai (MSR, New England) The Evolution of Proofs in Computer Science (abstract) Thu, 10:10-10:50 Irit Dinur (Weitzman Institute) Lifting locally consistent solutions to global solutions (abstract) Thu, 11:00-11:40 Benny Sudakov (ETH, Zurich) The minimum number of nonnegative edges in hypergraphs (abstract)

And now for my own lecture.

# BosonSampling and (BKS) Noise Sensitivity

Update (Nov 2014): Noise sensitivity of BosonSampling and computational complexity of noisy BosonSampling are studied in this paper by Guy Kindler and me. Some of my predictions from this post turned out to be false. In particular the noisy BosonSampling is not  flat and it does depend on the input matrix.  However when the noise level is a constant BosonSampling is in P, and when it is above 1 over the number of bosons, we cannot expect robust experimental outcomes.

—–

Following are some preliminary observations connecting BosonSampling, an interesting  computational task that quantum computers can perform (that we discussed in this post), and noise-sensitivity in the sense of Benjamini, Schramm, and myself (that we discussed here and here.)

## BosonSampling and computational-complexity hierarchy-collapse

Suppose that you start with n bosons each can have m locations. The i-th boson is in superposition and occupies the j-th location with complex weight $a_{ij}$. The bosons are indistinguishable which makes the weight for a certain occupation pattern proportional to the permanent of a certain n by n submatrix of the n by m matrix of weights.

Boson Sampling is a task that a quantum computer can perform. As a matter of fact, it only requires a “boson machine” which represents only a fragment of quantum computation. A boson machine is a quantum computer which only manipulates indistinguishable bosons with gated described by phaseshifters and beamsplitters.

BosonSampling and boson machines were studied in a recent paper The Computational Complexity of Linear Optics of Scott Aaronson and Alex Arkhipov (AA). They proved (Theorem 1 in the paper) that if (exact) BosonSampling can be performed by a classical computer then this implies a collapse of the computational-complexity polynomial hierarchy (PH, for short). This result adds to a similar result achieved independently by Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd (BJS) in the paper entitled: “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,” and to older results by  Barbara Terhal and David DiVincenzo (TD) in the paper Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games, Quant. Inf. Comp. 4, 134-145 (2004).

Since universal quantum computers can achieve BosonSampling (and the other related computational tasks considered by TD and BJS), this is a very strong indication for the computational complexity advantage of quantum computers which arguably brings us with quantum computers to the “cozy neighborhood” of NP-hardness.

Noisy quantum computers with quantum fault-tolerance are also capable of exact BosonSampling and this strong computational-complexity quantum-superiority applies to them as well.

## Realistic BosonSampling and Gaussian Permanent Estimation (GPE)

Aaronson an Arkhipov considered the following question that they referred to as Gaussian Permanent Approximation.

Problem (Problem 2 from AA’s paper): ($|GPE|_{\pm}^2$): Given as imput a matrix ${\cal N}(0,1)_{\bf C}^{n \times n}$ of i.i.d Gaussians,together with error bounds ε, δ > o, estimate to within additive error $\pm \epsilon n!$ with probability at leat 1-δ over X, in $poly(n,1/\epsilon,1/\delta)$ time.

They conjectured that such Gaussian Permanent Approximation is computationally hard and showed (Theorem 3) that this would imply that sampling w.r.t. states achievable by boson machines cannot even be approximated by classical computing (unless PH collapses). They regarded questions about approximation more realistic in the context of decoherence where we cannot expect exact sampling.

Scott Aaronson also expressed guarded optimism that even without quantum fault-tolerance BosonSampling can be demonstrated by boson machines for 20-30 bosons, leading to strong experimental evidence for computational advantage of quantum computers (or, if you wish, against the efficient Church-Turing thesis).

Is it so?

## More realistic BosonSampling and Noisy Gaussian Permanent Estimation (NGPE)

Let us consider the following variation that we refer to as Noisy Gaussian Permanent Estimation:

Problem 2′: ($|NGPE|_{\pm}^2$): Given as imput a matrix $M=$ ${\cal N}(0,1)_{\bf C}^{n \times n}$ of i.i.d Gaussians, and a parameter t>0 let NPER (M),  be the expected value of the permanent for $\sqrt {1-t^2}M+E$ where E= ${\cal N}(0,t)_{\bf C}^{n \times n}$.  Given the input matrix M together with error bounds ε, δ > o, estimate NPER(M) to within additive error $\pm \epsilon n!$ with probability at leat 1-δ over X, in $poly(n,1/\epsilon,1/\delta)$ time.

Problem 2′ seems more relevant for noisy boson machines (without fault-tolerance). The noisy state of the computer is based on every single boson  being slightly mixed, and the permanent computation will average these individual mixtures. We can consider the relevant value for t to be a small constant. Can we expect Problem 2′ to be hard?

The answer for Question 2′ is surprising. I expect that even when $t$ is very very tiny, namely $t=n^{-\beta}$ for $\beta <1$, the expected value of NPER(M) (essentially) does not depend at all on M!

## Noise Sensitivity a la Benjamini, Kalai and Schramm

Noise sensitivity for the sense described here for Boolean functions was studied in a paper by Benjamini Schramm and me in 1999.  (A related notion was studied by Tsirelson and Vershik.) Lectures on noise sensitivity and percolation is a new beautiful monograph by Christophe Garban and Jeff Steif which contains a description of noise sensitivity. The setting extends easily to the Gaussian case. See this paper by Kindler and O’donnell for the Gaussian case. In 2007, Ofer Zeituni and I studied the noise sensitivity in the Gaussian model of the maximal eigenvalue of random Gaussian matrices (but did not write it up).

Noise sensitivity depends on the degree of the support of the Fourier expansion. For determinants or permanents of an n by n matrices the basic formulas as sums of generalized diagonals describe the Fourier expansion,  so the Fourier coefficients are supported on degree-n monomials. This implies that the determinant and the permanent are very noise sensitive.

## Noisy Gaussian Permanent Estimation is easy

Noisy Gaussian Permanent Estimation is easy, even for very small amount of noise, because the outcome does not depend at all on the input. It is an interesting question what is the hardness of NGPE is when the noise is below the level of noise sensitivity.

Update (March, 2014) Exploring the connection between BosonSampling and BKS-noise sensitivity shows that the picture drawn here is incorrect. Indeed, the square of the permanent is not noise stable even when the noise is fairly small and this shows that the noisy distribution does not approximate the noiseless distribution. However the noisy distribution does depend on the input!

## AA’s protocol and experimental BosonSampling

Scott and Alex proposed a simple experiment described as follows : “An important motivation for our results is that they immediately suggest a linear-optics experiment, which would use simple optical elements (beamsplitters and phaseshifters) to induce a Haar-random $m \times m$ unitary transformation U on an input state of n photons, and would then check that the probabilities of various final states of the photons correspond to the permanents of $n \times n$ submatrices, as predicted by quantum mechanics.”

Recently, four groups carried out interesting BosonSampling experiments with 3 bosons (thus for permanents of 3 by 3 matrices.) (See this post on Scott’s blog.)

BKS-noise sensitivity is giving  simple predictions on how things will behave as a function of the number of bosons and this can be tested even with experiments with very small number of bosons. When you increase the number of bosons the distribution will quickly become uniform for the various final states. The correlation between the probabilities and the value corresponding to permanents will rapidly go to zero.

## Some follow-up questions

Here are a few interesting questions that deserve further study.

1) Does problem 2′ capture the general behavior of noisy boson machines? To what generality noise sensitivity applies for general functions described by Boson sampling distributions?

(There are several versions for photons-based quantum computers including even an important  model by Knill, Laflamme, and Milburn that support universal quantum computation. The relevance of BKS noise-sensitivity should be explored carefully for the various versions.)

2) Is the connection with noise sensitivity relevant to the possibility to have boson machines with fault tolerance?

3) What is the Gaussian-quantum analog for BKS’s theorem asserting that noise sensitivity is the law unless  we have substantial correlation with the majority function?

4) What can be said about noise-sensitivity of measurements for other quantum codes?

## A few more remarks:

### More regarding noisy boson machines and quantum fault tolerance

Noisy boson machines and BosonSampling are related to various other issues regarding quantum fault-tolerance. See my added recent remarks (about the issue of synchronization, and possible modeling using smoothed Lindblad evolutions) to my old post on AA’s work.

### Noise sensitivity and the special role of the majority function

The main result of Itai, Oded, and me was that a Boolean function which is not noise sensitive must have a substantial correlation with the majority function. Noise sensitivity and the special role of majority for it gave me some motivation to look at quantum fault-tolerance in 2005  (see also this post,) and this is briefly discussed in my first paper on the subject, but until now I didn’t find an actual connection between quantum fault-tolerance and BKS-noise-sensitivity.

### Censorship

It is an interesting question which bosonic states are realistic, and it came up in some of my papers and in the discussion with Aram Harrow and Steve Flammia (and their paper on my “Conjecture C”).

### A sort of conclusion

BosonSampling was offered as a way to prove that quantum mechanics allows a computational advantage without using the computational advantage for actual algorithmic purpose. If you wish, the AA’s protocol is offered as a sort of zero-knowledge proof that the efficient Church-Turing thesis is false.  It is a beautiful idea that attracted interest and good subsequent work from theoreticians and experimentalists. If the ideas described here are correct, BosonSampling and boson machines may give a clear understanding based on BKS noise-sensitivity for why quantum mechanics does not offer computational superiority (at least not without the magic of quantum fault-tolerance).

### Avi’s joke and common sense

Here is a quote from AA referring to a joke by Avi Wigderson: “Besides bosons, the other basic particles in the universe are fermions; these include matter particles such as quarks and electrons. Remarkably, the amplitudes for n-fermion processes are given not by permanents but by determinants of n×n matrices. Despite the similarity of their definitions, it is well-known that the permanent and determinant differ dramatically in their computational properties; the former is #P-complete while the latter is in P. In a lecture in 2000, Wigderson called attention to this striking connection between the boson and fermion dichotomy of physics and the permanent-determinant dichotomy of computer science. He joked that, between bosons and fermions, ‘the bosons got the harder job.’ One could view this paper as a formalization of Wigderson’s joke.”

While sharing the admiration to Avi in general and Avi’s jokes in particular, if we do want to take Avi’s joke seriously (as we always should), then the common-sense approach would be first to try to understand why is it that nature treats bosons and fermions quite equally and the dramatic computational distinction is not manifested at all. The answer is that a crucial ingredient for a computational model is the modeling of noise/errors, and that noise-sensitivity makes bosons and fermions quite similar physically and computationally.

### Eigenvalues, determinants, and Yuval Filmus

It is an interesting question (that I asked over Mathoverflow) to understand the Fourier expansion of the set of eigenvalues, the maximum eigenvalue and related functions. At a later point,  last May,  I was curious about the Fourier expansion of the determinant, and for the Boolean case I noticed remarkable properties of its Fourier expansion. So I decided to ask Yuval Filmus about it:

Dear Yuval

I am curious about the following. Let D be the function defined on {-1,1}^n^2
which associates to every +1/1 matrix its determinant.
What can be said about the Fourier transform of D? It looks to me that easy arguments shows that the Fourier transform is supported only on subsets of the entries
so that in every raw and columns there are odd number of entries. Likely there are even further restrictions that I would be interested to explore.
Do you know anything about it?
best Gil

Yuval’s answer came a couple of hours later like a cold shower:

Hi Gil,

The determinant is a sum of products of generalized diagonals.
Each generalized diagonal is just a Fourier character, and they are all different.

In other words, the usual formula for the determinant *is* its Fourier transform

This reminded me of a lovely story of how I introduced Moni Naor to himself that I should tell sometime.

### What else can a quantum computer sample?

The ability of quantum computers to sample (exactly) random complex Gaussian matrices according to the value of their permanents is truly amazing! If you are not too impressed by efficient factoring but still do not believe that QC can reach the neighborhood of NP-hard problems you may find this possibility too good to be true.

I am curious if sharp P reductions give us further results of this nature. For example,  can a QC sample random 3-SAT formulas (by a uniform distribution or by a certain other distribution coming from sharp-P reductions) according to the number of their satisfying assignments?

Can QC sample integer polytopes by their volume or by the number of integer points in them? Graphs by the number of 4-colorings?

# Noise Stability and Threshold Circuits

The purpose of this post is to describe an old conjecture (or guesses, see this post) by Itai Benjamini, Oded Schramm and myself (taken from this paper) on noise stability of threshold functions. I will start by formulating the conjectures and a little later I will explain further the notions I am using.

## The conjectures

Conjecture 1:  Let $f$ be a monotone Boolean function described by  monotone threshold circuits of size M and depth D. Then $f$ is  stable to (1/t)-noise where $t=(\log M)^{100D}$.

Conjecture 2:   Let $f$ be a monotone Boolean function described by  a threshold circuits of size M and depth D. Then $f$ is  stable to (1/t)-noise where $t=(\log M)^{100D}$.

The constant 100 in the exponent is, of course, negotiable. In fact, replacing $100D$ with any  function of $D$ will be sufficient for the applications we have in mind. The best we can hope for is that the conjectures are true if  $t$ behaves like  $t=(\log M)^{D-1}$.

Conjecture 1 is plausible but it looks difficult. The stronger Conjecture 2 while tempting is quite reckless. Note that the conjectures differ “only” in the location of the word “monotone”. Continue reading

# The Intermediate Value Theorem Applied to Football

My idea (in my teenage years) of how to become a professional basketball player was a bit desperate. To cover for my height and my athletic (dis)abilities, I would simply practice how to shoot perfectly from every corner of the court. I would not have to run or jump. My team could pass the ball to me at the right moment and I would shoot. (I was a little worried that once I mastered this ability they would change the rules of the game.)

But this idea did not work. As much as I practiced, I could not shoot perfectly from all corners of the court, and not even from the usual places. In fact, my shooting was below average (although not as much below average as my other basketball skills.)

Next came my idea how to become a professional football (soccer) player. This idea was based on mathematics, an area where I had some advantage over other ambitious sports people; more precisely, my idea was based on the intermediate value theorem. (We had a post about this theorem.)

The idea is this: If you put a football on your head and start running the ball will fall from behind. But if you put the ball on your forehead and start running the ball will fall in front of you. By the intermediate value theorem, there must be a point, in between, such that if you run with the ball at this point, the ball will not fall at all. In fact you can find such a point for every way you would like to run. And you can even learn to adjust it if you change your route!  The plan was now simple. At the right moment I would get the ball from my team, put it on the right point on my forehead  start running and slalom my way towards the goal. (I was a little worried that once I mastered this ability they would  change the rules of the game.) I practiced it for several weeks, 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