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 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.