More Reasons for Small Influence

influencecartoon1

Readers of the big-league ToC blogs have already heard about the breakthrough paper An average-case depth hierarchy theorem for Boolean circuits by Benjamin Rossman, Rocco Servedio, and Li-Yang Tan. Here are blog reports on Computational complexity, on the Shtetl Optimized, and of Godel Lost letter and P=NP. Let me mention one of the applications: refuting a 1999 conjecture by Benjamini, Schramm and me.

Update: Li-Yang Tang explained matters in an excellent comment below. Starting with: “In brief, we believe that an average-case depth hierarchy theorem rules out the possibility of a converse to Hastad-Boppana-LMN when viewed as a statement about the total influence of *constant*-depth circuits. However, while the Inf(f) <= (O(\log(S)))^{d-1} bound is often applied in the setting where d is constant,  it in fact holds for all values of d. It would interesting to explore the implications of our result in regimes where d is allowed to be super-constant.

Let me add that the bounded depth case is an important case (that I referred to here), that there might be some issues failing the conjecture for non-constant depth “for the wrong reasons”,  and that I see good prospect that RST’s work and techniques will refute BKS conjecture in full also for non-bounded depth.

Update:  Rossman, Servedio, and Tan refuted some important variations of our conjecture, while other variations remain open. My description was not so accurate and in hindsight I could also explained the background and motivation better. So rather than keep updating this post, I will write a new one in a few weeks. 

Boppana-Hastad-Linial-Mansour-Nisan-Boppana-Hastad

Theorem: If f is described by a bounded depth circuit of size s and depth d then I(f) the total influence of f,  is at most (\log s)^{d-1}.

The total influence I(f) of f is defined as follows: for an input x write I(x) for the number of neighbors y of x with f(y) \ne f(x). I(f) = \mathbb EI(x).

The history of this result as I  remember it is that: it is based on a crucial way on  Hastad Switching lemma going back to Hastad 1986 thesis, and for monotone functions one can use an even earlier 1984 result by Boppana.  It was first proved  (with exponent “d”) in 1993 by Linial-Mansour and  Nisan, as  a consequence of their theorem on the decay of Fourier coefficients for AC0 functions, (also based on the switching lemma). With the correct exponent d-1 it is derived from the switching lemma in a short clean argument in a 97 paper by Ravi Boppana; and finally it was extended to a sharpening of LMN result about the spectral decay by Hastad (2001).

Sipser MIT photo

Mike Sipser

Inverse Boppana-Hastad-LMN

Conjecture: (Benjanmini, Kala, and Schramm, 1999): Every Boolean function  f  is “close” to some depth-d size s circuit with (\log s)^{d-1} not much larger than I(f).

Of course, the exponent (d-1) is strongest possible but replacing it with some constant times d  is also of interest. (Also the monotone case already capture much interest.)

As we will see the conjecture is false even if the exponent d-1 is replaced by a constant times d. I do not know what is the optimal function u(d) if any for which you can replace the exponent d-1 by u(d).

Update: Following some comments by Boaz Barak I am not sure that indeed the new examples and results regarding them leads to disproof of our conjecture. The remarkable part of RST’s paper is that the RST example cannot be approximated by a circuit of smaller depth – even by one. (This has various important applications.) In order to disprove our conjecture one need to show that the influence of the example is smaller than what Boppana’s inequality ((log size)^{depth-1} ) gives. This is not proved in the paper (but it may be true). 

The RST’s result does say that if the influence is (say) logn (where n is the number of variables,) and the function depends on a small number of variables then it need not be correlated with a function in AC0.  

Anyway I will keep you posted.  

in 2007 O’Donnell and Wimmer showed that our inverse conjecture is false as stated. They took a Boolean function which is a tribe function on half the variables and “anti-tribes” on the rest. This still left the possibility that the exponent d-1 could be replaced by d or that “close” could be replaced by a weaker conclusion on substantial correlation.

Rossman,  Servedio, and  Tan.show a genuinely new reason for small influence!Their example, named after Mike Sipser,  is based on the AND-OR tree – a Boolean formula with alternating AND and OR levels and carefully designed parameters.  The crucial part is to show that you cannot approximate this function by lower depth circuits. The theorem proved by RST  is amazingly strong and does not allow reducing the depth even by one! The novel technique for proving it of random projections is very exciting.

It is still possible (I think) that such inverse theorems hold when the individual influences of all variables is below polylog(n)/n where n is the number of variables. Let me pose it as a conjecture:

Conjecture: Every Boolean function  f  with n variables and individual influences below polylog (n)/n is close to a function g in AC0   of size s depth d where (log s)^d is polylog (n).

And here is a post on TCSexchange with a question about “monotone  vs positive” for the class P. Similar questions for AC0 and TC0 were asked in this post.

This entry was posted in Combinatorics, Computer Science and Optimization, Open problems, Probability. Bookmark the permalink.

12 Responses to More Reasons for Small Influence

  1. Jon Awbrey says:

    See related concept of partial differentials for Boolean functions:

    http://inquiryintoinquiry.com/2015/05/11/survey-of-differential-logic-•-1/

    • Jon Awbrey says:

      The series of “Posts In Progress” (PIPs) where I began my attempt to understand Frankl’s Conjecture has a bunch of pretty pictures that I drew to illustrate partial and total differentials (local linear approximations) of boolean functions.

      Frankl Conjecture

  2. vznvzn says:

    ❗💡⭐ congratulations on your successfully “influential” yet-refuted conjecture!
    wondering if any of this can be tied into arithmetic circuit complexity which is advancing lately, havent seen tie-ins, but think they are likely to exist.

  3. Boaz Barak says:

    Hi Gil,
    Does RST’s ‘Sipser function” have low influence for a truly new reason? After all, I thought that the reason it has low influence is because it has a small depth circuit, no?

    BTW I gave a guest lecture on this result in Dana Moshkovitz’s class – the lecture notes (which are likely full of mistakes) can be found here http://www.boazbarak.org/Courses/avg_case_depth.pdf

    • Gil Kalai says:

      Dear Boaz thanks for the comment. Maybe I still miss something but I think that the low influence of the Sipser function cannot be derived from the (log size)^depth inequality. Lets think instead about the recursive majority on threes. (I would expect a similar result would apply there but dont know it.)
      The influence is n^beta for some power. log size ^ depth gives n^log n so it is not relevant. Our conjecture in a very weak form would say that recursive majority on threes can be approximated by size s depth d circuit where (log s)^d is poly (n) and if we believe that RST’s result extends to this example this would be false. I am not so happy with the term “a new reason” because the influence computation is easy here and so is, I suppose, for the Sipser function. It is that we do not have a unified reason for low influence in terms of circuit size and depth. It would be nice to state a general reason which explain why Sipser’s function’s influence or recursive majority are what they are. (So maybe Instead of writing “RST show a genuinely new reason for small influence!” I should say “RST shows that we do not know or even have a guess for a general reason for small influence!”

      • Boaz Barak says:

        It seems that their counter example applies the Sipser function on only a small number of variables, and so their proof of Theorem 3 (that a weak version of the BKS conjecture is false) does appeal to the (log size)^depth inequality just applied to a circuit of sqrt{log log n} depth on exp(exp(sqrt{log log n})) variables (the number of variables is also the size of the circuit).

        However, perhaps recursive majority can give a different example.

      • Gil Kalai says:

        Dear Boaz,

        There is still something which I am confused about. I thought that moving to a small number of variables is just to make the total influence polylog (n) so it will address one version of our conjecture perhaps by Ryan. But this is not needed to the way we think about the conjecture. The way I think about our conjecture if your function depends on a small number of variables just ignore the other variables. In our thinking and formulation the number of variables is irrelevant.

        Now, when you consider the Sipser function on m = exp exp sqrt log log n variables and the depth that RST uses (what is the depth precisely?) my impression is that a direct calculation of influence gives you something which is larger than m^{K depth} for every constant K. (If the influence is m^depth or so it is *not* a counter example to our conjecture – for our formulation you can just regard n to be m and there is no need to force the influence to be polylog (n) ).

        In any case, I think that the Sipser function on n variables with the correct parameters has influence which is substantially smaller than the log size ^ depth, and that the main difficulty is to show that you cannot approximate it by another circuit where (log s)^K depth explains the low influence witnessed.

  4. Boaz Barak says:

    I was referring to the proof of Theorem 3 in their paper (see page 8) which does seem to use Boppana’s theorem.
    I don’t know if a direct computation of influence will give another value

    • Gil Kalai says:

      Hmmm, it looks that I misunderstood the situation. If the influence is based on Boppana’s bound (BB) then it is *not* a counterexample to our conjecture. You need to show that the influence is BB^{o(1)} (or for stronger versions of the conjecture BB^alpha for alpha <1).

      Maybe (like in the case of recursive majority) the influence is smaller than BB. But this is needed to be shown. I suppose that the influence can be directly computed without referring to Boppana’s bound.

  5. Li-Yang Tan says:

    Gil, many thanks for mentioning our work on this blog, and for your kind words about our result. And thanks, Boaz, for lecturing about our result, and making your great lecture notes available online!

    We wanted to jot down a clarification in response to both your comments. In brief, we believe that an average-case depth hierarchy theorem rules out the possibility of a converse to Hastad-Boppana-LMN when viewed as a statement about the total influence of *constant*-depth circuits. However, while the Inf(f) <= (O(\log(S)))^{d-1} bound is often applied in the setting where d is constant, it in fact holds for all values of d. It would interesting to explore the implications of our result in regimes where d is allowed to be super-constant (indeed, we are discussing this with Gil now), but for this comment let me focus on the constant d regime (which is the regime the paper addresses). Let me elaborate…

    Fix \eps = 0.01. Conjecture 1 in our paper says that there exist universal constants d, K_1, K_2 such that every monotone f is 0.99-approximated by a depth-d circuit of size \exp((K_1 * \Inf(f))^{K_2}). Note that this conjecture captures Hamed's question (Problem 4.6.3 of http://cs.mcgill.ca/~hatami/comp760-2014/lectures.pdf) for functions of influence <= \log(n). (A major thrust of the O'Donnell-Wimmer paper was to rule out the possibility of having d=2 and K_2 = 1 in Conjecture 1.)

    We disprove Conjecture 1, and actually disprove the following even weaker conjecture:

    Conjecture 1': For every family {f_n} of n-variable monotone functions there exist *constants* d, K_1, and K_2 (all depending on the family but not n) such that f_n is 0.99-approximated by a depth-d circuit of size \exp((K_1 * \Inf(f))^{K_2}).

    Conjecture 1' captures the possibilities that are raised in (4) and (5) of http://cstheory.stackexchange.com/questions/12769/are-all-the-functions-whose-fourier-weight-is-concentrated-on-the-small-sized-se/14926#14926.

    Our counterexample to Conjecture 1' is the family of Sipser functions {S_n} of depth say (\log(n))^{0.49}. Our main result implies that for all fixed *constants* d, there is no depth-d circuit of size \exp(\poly(\Inf(f))) that even 51%-approximates S_n.

    In fact, our main result implies that the same statement holds for values of d up to (\log(n))^{0.49} – 1. It does not imply the statement for d = (\log(n))^{0.49} (note that S_n is itself a depth (\log(n))^{0.49} formula of linear size!) Therefore, our result does not rule out the possibility of a converse to Hastad-Boppana-LMN as stated in Gil's post above where d can be arbitrary (and need not be constant). Specifically, it is still possible that there exists a function \alpha such that the following holds: for every family {f_n} of monotone functions there exists a function d(n) and a constant K such that f_n is 0.99-approximated by a depth-d(n) circuit of size \exp((K * \Inf(f))^{1/\alpha(d(n)-1)}). (The [OW] result shows that this does not hold with \alpha being the identity function.)

    Hopefully what is written above is clear, but if not the following is one way to view our result within the context of the original BKS conjecture, O'Donnell-Wimmer's counterexample to the original BKS conjecture, and Hamed and Gil's subsequent questions. Focusing on the case of \log(n) influence functions,

    – The original BKS conjecture allowed for the possibility that every \log(n) influence function is 0.99-approximated by a \poly(n)-size depth-2 circuit.

    – O'Donnell-Wimmer gave a counterexample to this in their paper. Specifically, they proved the existence of a \log(n) influence function such that any 0.51-approximating depth-2 circuit must have size 2^{\Omega(n/\log(n))}.

    – However, [OW]'s hard function is a linear-size depth-3 circuit. Therefore, it is natural to wonder (as Hamed did in his lecture notes and Gil did in the CS theory StackExchange question) whether every \log(n) influence function is 0.99-approximated by a function in AC0.

    – We show that even this is not possible: there are \log(n) influence functions that cannot be 0.51-approximated by constant-depth circuits of quasi-polynomial size (indeed, even by \sqrt{\log\log(n)}-depth circuits of size \exp(\exp(\tilde{\Omega}(2^{\sqrt{\log\log(n)}})})).)

    Thanks again, Gil and Boaz, for your insightful comments and for pointing out these subtleties! We will be revising this section of the paper to clarify these issues.

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