When did Majority become the stablest? (Part 2)

The first question we’d like to answer is this: which is the monotone, balanced, transitive Boolean function which is least sensitive to bit-flips? We know that Majority is the worst possible with .

The new champion turns out to be the Tribes function first studied by Ben-Or and Linial. is a read-once DNF which is the OR of disjoint terms, each term is the AND of variables:

By choosing carefully, we get a (near)-balanced, transitive, monotone function where . So it beats Majority quite handily. But is this the best possible? Or can we hope to achieve sensitivity ? This would be optimal, since it is easy to argue an lower bound.

It turns out that in fact is the best possible. This follows from the celebrated result of Kahn, Kalai and Linial (KKL), which tells us that this is a lower bound on the sensitivity of any balanced Boolean function, where all variables have small influence. The Theorem is usually stated in terms of average sensitivity, which is . In our setting, the monotone and transitive conditions imply that no variable has influence more than , hence their result applies.

At first, Tribes might not seem as natural a function as Majority. So why does it turn out to be the least sensitive to bit-flips? For KKL to be tight, the Fourier expansion of tells us to look for a function which is concentrated on the first levels of the Fourier spectrum. This is equivalent to saying that is well-approximated by a polynomial of degree .  We know DNFs have such concentration. But why not something even simpler, like a decision tree that has (exact) degree ? It turns out that such functions will invariably have some “special” co-ordinates, and hence cannot be transitive. This is a relatively recent result by O’Donnell, Saks, Schramm and Servedio, which says that every degree Boolean function has a variable with influence . So we are back to CNF/DNFs and Tribes is about as simple as DNFs get.

Another natural example of a function that has low sensitivity (which I learnt from Yuval Peres): consider points on a circle. Assign a random bit to each. Define to be if the longest run of s is of length . For a suitable choice of , this function is near balanced. It is monotone, and further .

So given that Tribes beats Majority so handily for bit-flips, how does it fare under -noise for constant ? Not very well, it’s sensitivity approaches . Indeed, if you are looking for a function which is maximally sensitive, Tribes is not a bad choice.

So life is yet again complicated: there is no single functions that seems optimal for all settings of -noise. Indeed, this is why results on hardness amplification within NP which rely on composition with monotone functions need to switch from one function to another at various points. In contrast, if we don’t care about staying within NP, we can just use the XOR function.

But at the same time, perhaps a unified explanation is possible to explain the entire spectrum?

1. Is there an intuitive explanation for why the least sensitive function should look like a Hamming ball when is large, and look “Tribes-like” (Tribish? Tribal) when is small? In some sense, we got into this mess by disallowing co-ordinate functions, which are essentially sub-cubes. Are these the functions that “look” most like sub-cubes (from some strange angle)?
2. Is there an inverse result which interpolates smoothly between KKL and Majority is the Stablest? Given that these are two of the most powerful theorems  in all of Boolean function analysis, it would have to be quite a theorem.

Parikshit.