Influence, Threshold, and Noise

 

poster4.1

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.

Influence, Threshold, and Noise:

Part I: Influence

ai1c

 

Boolean functions (under different names and different notation) occur in my field – combinatorics and in many other areas of mathematics, computer science, and other sciences.

 

ai2c

So the influence of the th variable on a Boolean function f is the probability that for a random 0-1 vector changing the value of the kth coordinate will change the value of f. This notion, in much greater generality, was studied by Ben-Or and Linial in the context of “collective coin flipping.”

See the post on Nati’s influence.

 

ai3

 

Understanding total influence of Boolean functions amounts to a detailed understanding of the expansion properties of a single graph – the graph of the discrete cube. The edge isoperimetric theorem (and its sharper forms) is a very important result in combinatorics from the ’70s by Harper, Hart and others.

For balanced Boolean functions (those with \mathbb E (f) bounded away from zero and one,) we can say more on the individual influence

ai4

Let me end this part of the lecture with an open problem:

ai5c

Inverse theorems of this kind are very important in extremal and additive combinatorics. We can also ask for a descriptions of Boolean functions f for which I(f) \le (1+o(1)) {\mathbb E}(f)\log (1/{\mathbb E}(f)). But note that this version of the edge-expansion inequality is sharp only for certain values of \mathbb E (f).

For more questions on inverse theorems for Boolean functions see this lecture at the Simons Institute.

The dilemmas  I have when giving a general-audience talk of this kind is how to balance old and new things, how not to put too much material into a single lecture, and how to avoid the temptation to talk about two new research directions rather than about one.   

Part II: Projections

In this part I talk about the paper: J. Bourgain, J. Kahn and G. Kalai, Influencial coalitions for Boolean functions.

ai6

The projection of A to the subcube \Omega(T) consists of those vectors in \Omega(T) for which you can assign values to the variables not in T, and get a vector in A. Note that influence of a variable k, is precisely the gap between the expectation of A and the expectation of the projection of A to all coordinates except k.

I hope that this is clear. Defining the projection precisely with mathematical formulas can be cumbersome. Also there is a dilemma regarding notation. I can refer to the Ben-Or-Linial influence of large sets (it is equal to \mu(A_S)-\mu(A) where S is the complement of T), and I can also refer to “traces” which is a standard name for projection. But I think that for a wide-audience lecture talking about projection is better.

ai7

 For more on the Sauer-Shelah (shattering) lemma see this post.

I will now let the results with Jeff and Jean speak for themselves:

ai8ai9ai10

As you can see from the last two slides, we still have a huge gap for Problem 3. Problem 3 feels to me similar to other cases where there is an exponential gap between what the “incremental density increase method” gives and what the best constructions give. Roth’s theorem for subsets of [n] without 3-term arithmetic progressions and the related cup set problem are two other examples.

For the cap set problem see e.g. here, here and here. There is some similarity between problem and techniques between additive combinatorics (and pseudorandomness) and influences and other isoperimetric questions. Still moving more techniques and ideas across could, perhaps, be useful.

ai11c

 

ai12

Somehow we thought about this very natural question only after finishing our project.

 

Part III: Threshold

Threshold behavior and the sharp threshold phenomena are closely related to influences. Here we consider a more general (Bernoulli) probability distribution on \Omega_n, depending on a parameter p and study how the expected value of a monotone Boolean function changes with p. The connection to influence is via a fundamental lemma of Russo. I will mention one related conjecture about random graphs.

ai13

Jeff and I worked hard to try to find counterexamples to the conjecture, but instead we mainly succeeded to extend and strengthened the conjectures in various directions. We expect that inverse theorems and in particular an answer to Problem 1 will be crucial for a (positive) solution of this conjecture.

Here is the link to my paper with Kahn Thresholds and expectation thresholds. Here is a link to a survey article by Muli Safra and me entitled thresholds phenomena and influence.

 

Part IV: Noise

 

ain1

In the lecture I will informally explain what the crossing event for critical planar percolation is.

infinitepath

Itai Benjamini contributed many inspiring questions and ideas about noise-sensitivity over the years. In particular, he raised questions about noise sensitivity and random matrices in the late 90s.

ain2

I am thinking of adding another problem:

Problem: Show that the crossing event for critical percolation in 3-space is noise-sensitive.

Part V: Fourier

Discrete harmonic analysis has become an important tool in the study of Boolean functions. From time to time (enough to make us happy) this tool helps, and it has led to various interesting questions as well. I will keep Fourier pretty much in the background for this talk.

aif1c

aif2

Part VI: Quantum

Quantum computation is an important area and meeting point of computer science, physics, engineering, and mathematics. It offers the possibility of vastly quicker algorithms for certain problems. This possibility, yet to be realized, is referred to as quantum supremacy. We will discuss a quick forceful path towards quantum supremacy offered by Scott Aaronson and Alex Arkhipov.

aiq1

Computing or even approximating permanents is a notoriously difficult questions. Efficient classical (or even quantum) algorithms are not expected.

aiq2cc

There are several experimental groups over the world attempting to implement BosonSampling using various techniques.

aiq3c

Noise sensitivity proposes an explanation for why BosonSampling will not work.

aiq4

Here are the results with Guy Kindler.

aiq5cc

The most damaging aspect of this theorem is the noise-sensitivity part. I expect both parts of the theorem to apply to other forms of noise considered for BosonSampling (there is quite a bit left to prove, though). Moreover, noise sensitivity, means that we will have strong dependence on the noise itself.

A potential relevant story: There is a nice story of Ephraim Kishon (that Nati told me) of some relevance: A guy meets a salesman on the street selling a magical cleaning liquid. The salesman puts a dirty shirt inside water, adds this liquid and remarkably the shirt gets cleaned. So the guy buys a bottle with the liquid and shows it to his wife. He puts some ink on a shirt, puts it in water, add the cleaning liquid and, lo and behold, nothing happens, in fact, the ink is smeared all over the shirt. The guy rushes back to the salesman and complains that the cleaning liquid does not work.

“No,” explains the salesman, “the cleaning material is perfectly fine.” “But,” offering him another bottle, “instead of ink you need to use this material for making the shirt dirty in the first place.”

We can expect that the noise will depend on doubly-exponential many parameters in terms of the number of bosons, or even triply-exponential if undesirable interactions between the bosons are also assumed.

 

aiq6aiq7

I expect that this picture will “kick in” for a small number of bosons. We are going to  witness it moving from 3 bosons to 4 and from 4 bosons to 5.  However, some other researchers in this area see various reasons for optimism that the noise level can be pushed below 1/n. Of course, it will be very exciting to check it experimentally.

The sharpness of Item B (for a somewhat different model of noise) is a result by Alex Arkhipov (private communication), and the sharpness of item C is a result (partially heuristic and again for a different noise model) by Scott Aaronson (private communication).   

aiq9

I am very interested in the last item, and I have something to show you. But first let me mention a fascinating question in quantum computational complexity.

BosonSampling raises interesting theoretical questions and even if it cannot work standing alone it can be useful as a quick way for “quantum supremacy” combined with quantum fault-tolerance (if quantum fault-tolerance is possible).

(I think that this problem was first proposed in this post.)

aiq10

Here, we hope for a result that if BQP-computer can perform QuantumSampling then this leads to an unlikely collapse of complexity classes (we cannot expect absolute results).

Part VII: Movie

I plan to end by showing 3 minutes from my overview movie on quantum computers.

 

About these ads
This entry was posted in Combinatorics, Computer Science and Optimization, Conferences, Probability, Quantum and tagged , , , , , , , . Bookmark the permalink.

3 Responses to Influence, Threshold, and Noise

  1. John Sidles says:

    If anyone (students especially) wishes to numerically experiment with Gil’s and Guy’s permanent-computing ideas, the Mathematica StackExchange question “Can (compiled) matrix permanent evaluation be further sped-up?” provides code that requires only a few milliseconds to evaluate permanents for matrices up to 20×20, with 25×25 matrices as a practical limit for laptop-scale computation.

    In regard to noise-sensitivity of permanents, my personal numerical experience is broadly consonant with Gil and Guy’s scaling result.

    Moreover, even in the event that 1/n noise levels prove to be achievable in BosonSampling experiments, and furthermore that permanents are rigorously NP-hard to estimate in this limit, then none-the-less there can exist stratagems by which a PTIME-limited simulationist “Bob” can simulate ScatterShot BosonSampling experiments indistinguishably from an n-photon experimentalist “Alice.”

    Whether Alice’s n-photon BosonSampling experiments are practical, and whether Bob’s n-photon PTIME simulation stratagems are practical, both are important open questions, and it is entirely reasonable (as it seems to me) that we may hope and even expect that Alice and Bob’s ambitions both may be fulfilled.

    Conclusion  There is ample scope for further algorithmic improvements in both permanent estimation for matrices+noise, and the (broader) problem of permanent estimation/simulation for ScatterShot-sampled matrices+noise.

    • Gil Kalai says:

      Dear John, indeed there are various variations that I would love to test numerically and I am aware also of much more detailed numerical simulations of certain proposed implementations of BosonSAmpling. I hope to start looking for how to implement it later this summer.

  2. Paul says:

    Curious paper about P versus NP problem

    http://hal.archives-ouvertes.fr/hal-00984866

    Do you think is a serious proof?

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