Matemática Computacional: 9 feb 2010

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 $f$ be a monotone Boolean function described by monotone threshold circuits of size M and depth D. Then $f$ is stable to (1/t)-noise where $t=(\log M)^{100D}$ .

Conjecture 2: Let $f$ be a Boolean function described by monotone threshold circuits of size M and depth D. Then $f$ is stable to (1/t)-noise where $t=(\log M)^{100D}$ .

The constant 100 in the exponent is, of course, negotiable. In fact, replacing $100D$ with any function of $D$ will be sufficient for the applications we have in mind. The best we can hope for is that the conjectures are true if $t$ behaves like $t=(\log M)^{D-1}$ .

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 $n=3^m$ . 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 $TC_0$ .

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

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

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

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 $f$ be a Boolean function of $n$ variables $x_1,x_2.\dots,x_n$ . Let $t>0$ be a small real number. Assign values to the variables uniformly at random and then consider $y_1,y_2,\dots,y_n$ such that $y_i=x_i$ with probability $1-t$ and $y_i=1-x_i$ with probability $t$ .

Fix a constant $\epsilon = 0.0000001$ . We say that a Boolean function $f$ with n variables is stable to noise $t$ if the probability that $f(x_1,x_2,\dots, x_n) \ne f(y_1,y_2,\dots, y_n)$ is below $\epsilon$ .

A threshold function is a function of the form: $f(x_1,x_2,\dots,x_n)=sgn(\sum w_ix_i)$ , where $w_1,w_2\dots w_n$ 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 mentioned circuits in this post.) A monotone threshold circuit is a threshold circuit in which all gates are monotone threshold functions.

The $AC_0$ analogs

Here is briefly the situation for $AC_0$ .

Theorem (Boppana): If f is a function that can be described by a depth D size M monotone Boolean circuit then $I(f) \le C(\log M)^{D-1}$ .

Here $I(f)$ denotes the total influence of $f$ . 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 $I(f) \le C(\log M)^{D-1}$ .

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 $\{\sum \hat f^2(S):|S|=t\}$ decays exponentially with $t$ when $t>C(\log M)^{D-1}$ (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 $AC_0$ that are not in Monotone $AC_0$ . (Here is the paper!)

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

Formally we ask, for every fixed real $\epsilon>0$ and integers $d>0,~c>0,~d'\ge d,$ and $c' \ge c$ , for a sequence of monotone functions $f_n$ of depth d and size at most $Kn^c$ ( $K$ and $c$ are fixed constants and $f_n$ is a function on $n$ variables), such that:

The distance between $f_n$ and every function $g$ that can be expressed by a depth $d'$ , size $n^{c'}$ monotone Boolean circuit is at least $\epsilon$ .

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

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

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

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.

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 $\epsilon$ -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.

Small 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 $f$ 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 that if a function described by a bounded depth monotone threshold circuit is balanced (namely, the probability for $f=1$ 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.