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 be a monotone Boolean function described by monotone threshold circuits of size M and depth D. Then is stable to (1/t)-noise where .

**Conjecture 2:** Let be a monotone Boolean function described by a threshold circuits of size M and depth D. Then is stable to (1/t)-noise where .

The constant 100 in the exponent is, of course, negotiable. In fact, replacing with any function of will be sufficient for the applications we have in mind. The best we can hope for is that the conjectures are true if behaves like .

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”. (In the first conjecture the first appearance of “monotone” is not essential since every function that can be described by a monotone threshold circuit is monotone.)

## Recursive majority on 3s

There are many Boolean functions that are very noise sensitive. A simple example is the recursive majority on 3s (RM3), defined as follows: Suppose that . Divide the variables into three equal parts. Compute the RM3 separately for each of these parts and apply the majority to the three outcomes.

## Computational complexity consequences

**C1** (To Conjecture 1): The RM3 is not in Monotone .

**C2** (To Conjecture 1): 2. The RM3 cannot be approximated by a function in Monotone .

**C3** (To Conjecture 2): The RM3 is not in .

**C4** (To Conjecture 2): The RM3 cannot be approximated by a function in .

The first consequence, may already follow from results by Andy Yao and by Johan Hastad and Mikael Goldman. (See this paper. They talked about the “AND/OR-tree” rather than RM3.)

Of course, we can replace RM3 with other noise-sensitive properties. For example, we can take the crossing event in planar percolation which is closely related to the problem of “s-t connectivity”. (See this post about noise sensitivity.) We can extend the conjectures by replacing the uniform probability distribution by other product probability distributions; doing so will allow us to replace RM3 by the AND/OR-tree. It is reasonable to believe that all these conjectures are true, but also that C3 and C4 are extremely difficult. I would also not underestimate the gap between the exact conjectures C1 and C3 and the approximate conjectures C2 and C4. Showing that RM3 cannot even be approximated by a function described by monotone (or general monotone) threshold circuit of bounded depth and polynomial size might be very hard. Maybe RM3 **does** admit such an approximation.

## Some basic definitions

Let be a Boolean function of variables . Let be a small real number. Assign values to the variables uniformly at random and then consider such that with probability and with probability .

Fix a constant . We say that a Boolean function with n variables is **stable to noise** if the probability that is below .

A **threshold function** is a function of the form: , where are real weights. If all weights are nonnegative the function is called a monotone threshold function (or a weighted majority function).

A **threshold circuit** is a circuit all whose gates are threshold linear functions. (We discussed circuits and complexity in this post.) A **monotone threshold circuit** is a threshold circuit in which all gates are monotone threshold functions.

## The analogs

Here is briefly the situation for .

**Theorem (Boppana):** If f is a function that can be described by a depth D size M monotone Boolean circuit then .

Here denotes the total influence of . See this post about influence.

The famous Hastad switching lemma allows us to prove

**Theorem (Hastad-Boppana):** If f is a function that can be described by a depth D size M monotone Boolean circuit then .

**Theorem (Linial Mansour Nisan; improved by Hastad)** : If f is a function that can be described by a depth D size M monotone Boolean circuit then decays exponentially with when (See the original papers for the precise formulation and the meaning of “decay exponentially”.)

## Positive vs. Monotone

We regard consequences C1/C2 as plausible, but consequences C3/C4 as extremely difficult. But can we present a single example of a function for which C3/C4 apply but not C1/C2? This is also difficult!

** **

**Theorem (Miklós Ajtai and Yuri Gurevich):** There are monotone functions in that are not in Monotone . (Here is the paper!)

**Problem 1**: Are there monotone functions in that cannot be approximated by functions in Monotone ?

Formally we ask, for every fixed real and integers and , for a sequence of monotone functions of depth d and size at most ( and are fixed constants and is a function on variables), such that:

The distance between and every function that can be expressed by a depth , size monotone Boolean circuit is at least .

**Problem 2:** Are there monotone functions in that are not in Monotone ?

**Problem 3:** Are there monotone functions in that cannot be approximated by functions in Monotone ?

## Natural proofs barrier?

One reason to be suspicious about Conjecture 2 is the famous natural proof barrier in computational complexity pioneered by Rasborov and Rudich. A class of functions that allows the creation of pseudo random generators cannot be separated by a “natural proof”. Moni Naor and Omer Reingold described pseudorandom functions in .

A natural proof is very roughly a method that distinguishes a low complexity function from a typical Boolean function. You should not be satisfied by this very rough description and read Dick Lipton’s post “Who’s afraid of natural proofs” or the original paper or many other sources. (See also the series of posts by Gowers starting with this one. Our Conjectures 1 and 2 were briefly discussed there in the remarks section.)

A random monotone Boolean function is noise stable. In fact a random monotone Boolean function is very close to the majority function. So the natural proof barrier does not apply automatically to Conjecture 2.

Dick Lipton suggested in his post (in a specific way that we will not repeat here) that monotonicity may be used to get around the natural proof barrier. The property of being monotone is fairly mysterious and we do not understand it well enough. As we mentioned, typical monotone functions are very much like the majority function.

Suppose we want to prove that NP is different from P by presenting a property X of monotone Boolean functions such that monotone Boolean function which satisfy X are not in P, and are not even -close to P. We may expect that such a property X will **not hold** for random monotone Boolean functions, as the latter are so similar to simple majority. Does this give some hope to get around the natural proof barrier? Probably not more than a faint hope. (It is difficult to imagine a proof technique that will use monotonicity of a target function for non monotine circuits.) In any case, we should take note of it:

**Question:** Does monotonicity give a way to get arround the natural proof barrier?

A more promising avenue is going from the computer science constructions to combinatorics and probability questions. One interesting direction would be to try to use the constructions of Boolean functions coming from cryptography and complexity, such as the Naor-Reingold construction, to shed light on combinatorial and probabilistic properties of Boolean functions.

## Remarks

It is not obvious that weighted majority functions are noise stable. Here is a sharp argument by Yuval Peres.

Some small remarks about Conjecture 1: a Boolean function described by a two-round majority represents a threshold circuit of depth two. Proving noise stability for two-round majority is easy by induction. If you use the same variable more then once then things get more complicated. (I do not have a clue for the case that you allow negative weights.) With Ravi Kannan we looked at monotone threshold circuits of depth two, and noticed that in some cases we can deduce from noise stability of the functions described by the gates that the function itself is not completely noise-sensitive to the required level of noise. (But this is considerably weaker than what we really need.)

One can conjecture We conjectured in the paper that if a function described by a bounded depth monotone threshold circuit is balanced (namely, the probability for is bounded away from 0 and from 1) then it is stable to a constant level of noise. However, Jean Bourgain gave an example showing that this is not the case.

Another conjecture in the paper is a “reverse” version of the theorems by Hastad and Boppana: if a [monotone] Boolean function has “small influence” then it can be approximated by a [monotone] circuit of “small” depth and size. The strongest possible version of this conjecture was disproved by R. O’Donnell, K. Wimmer: *Approximation by DNF: examples and counterexamples* (pdf)

.

## Polynomial threshold gates.

There is fruitful recent research on functions that can be expressed as signs of low degree polynomials.

Updates: An interesting related post can be found in “In theory“.

A (failed) attempt to distingish using the Fourier distribuion Boolean functions in ACC is offered by me here.

MassimoDear Gil,

in Conjecture 2 you did’t mean *monotone* threshold circuits, did you?

Gil KalaiPost authorDear Massimo, corrected thanks!

This reminds me that when I was a student a professor in calculus came to class and said:

“Students, last time we proved a lower bound and today we will prove a lower bound.”

He saw that the students are puzzled so he immediately corrected himself and said:

“Last time we proved an

upper boundand today we will prove an upper bound.”After some scattered laughs and uneasiness at class he realized that he had made a mistake and said:

“I am very confused today, first, I said twice lower bound and then I said twice lower bound!”.

RahulLoved the exclamation mark after the mention of Ajtai-Gurevich. Wish there were a comprehensible version of that argument…

Ryan WilliamsI am not sure how much this helps in understanding your conjectures, but it appears that in order to prove that RM3 is not in TC^0, it suffices to prove that there is an eps > 0 such that RM3 does not have TC0 circuits of size n^{1+eps}.

The idea is to think like Allender and Koucky do in their recent paper:

http://eccc.hpi-web.de/eccc-reports/2008/TR08-038/index.html

We prove the contrapositive. Suppose RM3 has TC0 circuits of size O(n^k). Due to its recursive structure, RM3 on 3^m inputs can be expressed as a depth O(k/eps) circuit of O(3^m) size, where the basis gates of the circuit are “RM3 on O(3^{eps m/k}) inputs”. Substitute in your O(n^k) circuits for the basis gates: now you have a TC0 circuit for RM3 with O(3^{m + eps m}) <= O(n^{1+eps}) size.

Gil KalaiPost authorDear Ryan, this is very interesting!

JohnnyGreat site and a very informative post. Keep up the great work!

Pingback: Analysis of Boolean Functions | Combinatorics and more

Pingback: Circuit Lower Bounds by Properties and by Brute Force « in theory

Gil KalaiThere are even weaker questions about the relation between “positive” and “monotone”. Let f be a monotone balanced Boolean function in TC0. (Here by balanced I mean that the probability that f=1 is between 1/10 and 9/10.) Can we find a balanced boolean function g in TC0 so that the correlation between G and f is larger than (say) 1/100. A positive answer suffices to reduce the conjecture for TC0 (In a slightly weaker form) to the conjecture for “monotone TC0″. One can ask a similar quastion for AC0.

Pingback: Noise Sensitivity and Percolation. Lecture Notes by Christophe Garban and Jeff Steif | Combinatorics and more

Pingback: BosonSampling and (BKS) Noise Sensitivity | Combinatorics and more

Pingback: A Tighter Grip on Circuit Depth | Gödel's Lost Letter and P=NP

Pingback: More Reasons for Small Influence | Combinatorics and more