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.

Contact person: Gil Kalai,
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:

Continue reading

Analysis of Boolean Functions – week 1

Home page of the course.

In the first lecture I defined the discrete n-dimensional cube and  Boolean functions. Then I moved to discuss five problems in extremal combinatorics dealing with intersecting families of sets.

1) The largest possible intersecting family of subsets of [n];

2) The largest possible intersecting family of subsets of [n] so that the family of complements is also intersecting;

3) The largest possible family of graphs on v vertices such that each two graphs in the family contains a common triangle;

4) Chvatal’s conjecture regarding the maximum size of an intersecting family of sets contained in an ideal of sets;

5) Erdos-Ko-Rado Theorem.

Exercise: Prove one of the following

a) The Harris-Kleitman’s inequality

b) (from the H-K inequality) Every family of subsets of [n] with the property that every two sets have non-empty intersection and no full union contains at most 2^{n-2} sets.

More reading: this post :”Extremal combinatorics I: extremal problems on set systems“. Spoiler: The formulation of Chvatal’s conjecture but also the answer to the second exercise can be found on this post: Extremal combinatorics III: some basic theorems. (See also peoblen 25 in the 1972 paper Selected combinatorial research problems by Chvatal, Klarner and Knuth.)


I moved to discuss the problem of collective coin flipping and the notion of influence as defined by Ben-Or and Linial. I mentioned the Baton-passing protocol, the Alon-Naor result, and Feige’s two-rooms protocol.

More reading: this post :” Nati’s influence“. The original paper of Ben-Or Linial:  Collective coin flipping, M. Ben-Or  and N. Linial, in “Randomness and    Computation” (S. Micali ed.) Academic Press, New York, 1989, pp.    91-115.

Tentative Plans and Belated Updates II


Elementary school reunion: Usually, I don’t write about personal matters over the blog, but having (a few weeks ago) an elementary school reunion after 42 years was a moving and exciting event as to consider making an exception. For now, here is a picture:


Jirka’s Miraculous year

It looks like a lot is happening. From time to time I think that I should tell on my blog about exciting new things I hear about, but this is quite a difficult task. Perhaps I should at least post updates about progress on problems I discussed earlier, but even this is not easy.  Jirka Matousek wrote a paper entitled The dawn of an algebraic era in discrete geometry?  The paper starts as follows:

To me, 2010 looks as annus mirabilis, a miraculous year, in several areas of my mathematical interests. Below I list seven highlights and breakthroughs, mostly in discrete geometry, hoping to share some of my wonder and pleasure with the readers.

The paper lists seven startling new results. A few of these results were discussed here, a few others I have planned to discuss later, and yet a few others (like the recent solution by June Huh of the famous unimodularity conjecture for the coefficients of chromatic polynomials of graphs) caught me by a complete surprise. (Here is a link to a follow up paper by June Huh and Eric Katz.) Let me add one additional item, namely the solution (in the negative) by Boris Bukh of Eckhoff’s partition conjecture.

Other wonderful combinatorics news

These are also good times for other areas of combinatorics. I described some startling developments (e.g., here and here and here) and there is more. There were a few posts (here and here) on the Cup Set Problem. Recently Michael Bateman and Nets Katz improved, after many years, the Roth-Meshulam bound.  See these two posts on Gowers’s blog (I,II). Very general theorems discovered independently by David Conlon and Tim Gowers and by Matheas Schacht show that many theorems (such as Ramsey’s theorem or Turan’s theorem) continue to hold for substructures of sparse random sets.  Louis Esperet, Frantisek Kardos, Andrew King, Daniel Kral, and Serguei Norine proved the Lovasz-Plummer conjecture. They showed  that every cubic bridgeless graph G has at least 2^(|V(G)|/3656) perfect matchings. The concept of flag algebras, discovered by Razborov, is an extremely useful tool for extremal set theory. It has led to solutions of several problems and seems to bring us  close to a solution of  Turan’s Conjecture (which  we discussed here and here.) For example, it led to the solution by Hamed Hatami, Jan Hladký, Daniel Král, Serguei Norine, and Alexander Razborov of the question on the maximum number of pentagons in triangle-free graphs.  Hamed Hatami found a structure theorem for Boolean functions with coarse thresholds w.r.t. small probabilities. This extends and sharpens results by Ehud Friedgut and Jean Bourgain. I finally caught up (thanks to Reshef Meir) with Moser-Tardos result giving a new algorithmic proof for Lovasz local lemma. Amazing! You can read about it here.

Some updates on my Internet questions

Imre Leader and Eoin Long wrote a paper entitled tilted Sperner families, which solves a question I raised in the context of polymath1. Imre and Eoin give additional results and conjectures. My motivation was to try to come up (eventually) with very very general conjectures which include density Hales-Jewett as a very special case and are also related to error-correcting codes. Raman Sanyal discovered a dual form of Tverberg’s theorem in terms of families of fans.  (We asked about it here.) There is a new paper on the Entropy-Influence conjecture entitled The Fourier Entropy-Infuence Conjecture for certain classes of Boolean functions, by Ryan O’Donnell, John Wright, and Yuan Zhou, The paper contains a proof of the conjecture for symmetric Boolean functions and  various other cases. This is the first new result on the conjecture for many years. Also there is nice progress for the AC^0-prime number conjecture asked about in a previous post, and a subsequent Mathoverflow question (There I will keep updating matters.). Ben Green solved the conjecture! Jean Bourgain settled the more general MO question and also found results on certain AC(2) circuits.

Newton Institute and Oberwolfach,

And it seems that things are moving along nicely in other areas close to my heart.  A week ago (This was actually two months ago)  I participated in a workshop at the Newton Institute on discrete harmonic analysis. And in the first week of February we had our traditional Oberwolfach meeting on geometric and topological combinatorics. Many interesting results!

A visit to IQI

In the last week of January I visited Caltech. I missed the IPAM meeting scheduled a week before because my visa arrived too late but I still made it to IQI. This was a very nice opportunity as most of my time at Caltech was devoted to quantum information/quantum computation issues related to my own work on quantum fault tolerance. So I gave an “informal” seminar describing my point of view (and gave it again the next day at USC). Here are the slides.  My lecture was followed by two-hour discussion of the more technical details of my conjectures, seeking weak points and counterexamples in what I said, and trying to associate it with physics. There followed further discussions about some aspects of quantum fault tolerance and more general questions of quantum information with John Preskill, Leonard Schulman, Daniel Lidar and a few other people. (A lot of brilliant young people!) I learned quite a lot and was happy with this opportunity. (Of course, I did talk a little with Caltechian old and new friends about bona fide combinatorics questions.)

Three jokes for a dollar

On the weekend I took the LA metro (whose mere existence surprised me) and visited downtown LA and Hollywood. Next to Pershing station a person stopped me and asked if I want to buy three jokes for one dollar. I first said no, but then I reconsidered, called him back and gave him a dollar. To his disappointment and mine I did not understand the first joke, but the other two (perhaps adjusted to my revealed level of understanding) were quite good.

Hectic semester at HUJI

Here at Huji things are as hectic as always with 10-15 weekly research seminars. This week (This was two months ago; the semester have just ended). Continue reading

Nati’s Influence

When do we say that one event causes another? Causality is a topic of great interest in statistics, physics, philosophy, law, economics, and many other places. Now, if causality is not complicated enough, we can ask what is the influence one event has on another one.  Michael Ben-Or and Nati Linial wrote a paper in 1985 where they studied the notion of influence in the context of collective coin flipping. The title of the post refers also to Nati’s influence on my work since he got me and Jeff Kahn interested in a conjecture from this paper.


The word “influence” (dating back, according to Merriam-Webster dictionary, to the 14th century) is close to the word “fluid”.  The original definition of influence is: “an ethereal fluid held to flow from the stars and to affect the actions of humans.” The modern meaning (according to Wictionary) is: “The power to affect, control or manipulate something or someone.”

Ben-Or and Linial’s definition of influence

Collective coin flipping refers to a situation where n processors or agents wish to agree on a common random bit. Ben-Or and Linial considered very general protocols to reach a single random bit, and also studied the simple case where the collective random bit is described by a Boolean function f(x_1,x_2,\dots,x_n) of n bits, one contributed by every agent. If all agents act appropriately the collective bit will be ‘1’ with probability 1/2. The purpose of collective coin flipping is to create a random bit R which is immune as much as possible against attempts of one or more agents to bias it towards ‘1’ or ‘0’. Continue reading