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 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.
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 .
The total influence of is defined as follows: for an input write for the number of neighbors y of x with . .
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).
Conjecture: (Benjanmini, Kala, and Schramm, 1999): Every Boolean function f is “close” to some depth-d size s circuit with 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 ( ) 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 is polylog (n).