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 monotone Boolean function described by  a 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 discussed circuits and complexity 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. (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 \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. 

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 We conjectured in the paper 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.

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.

About these ads
This entry was posted in Combinatorics, Computer Science and Optimization, Probability and tagged , , , , . Bookmark the permalink.

11 Responses to Noise Stability and Threshold Circuits

  1. Massimo says:

    Dear Gil,

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

  2. Gil Kalai says:

    Dear 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 bound and 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!”.

  3. Rahul says:

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

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

  5. Gil Kalai says:

    Dear Ryan, this is very interesting!

  6. Johnny says:

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

  7. Pingback: Analysis of Boolean Functions | Combinatorics and more

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

  9. Gil Kalai says:

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

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s