This is a question that I've been pondering, on and off, for a while, and unsuccessfully. I'd be very interested in any insight regarding this conjecture. (Or rather, these conjectures.)

Recall that, given a Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$, the Kahn—Kalai—Linial theorem states that $$\max_{i\in[n]} \operatorname{Inf}_i f \geq \operatorname{Var}[f]\cdot \Omega\!\left(\frac{\log n}{n}\right) \tag{1} $$ from which we get that, for any monotone Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$, $$\max_{i\in[n]} \widehat{f}(i) \geq \operatorname{Var}[f]\cdot \Omega\!\left(\frac{\log n}{n}\right) = (1-\widehat{f}(0)^2)\cdot \Omega\!\left(\frac{\log n}{n}\right) \tag{2} $$ (writing $\widehat{f}(i)$ for $\widehat{f}(\{i\})$, $i\in\{0,\dots,n\}$). Moreover, (2) is tight, as shown by considering the $\textsf{Tribes}_n$ function. In particular, this implies that $$ W^{(0)}[f]+W^{(1)}[f] = \sum_{i=0}^n \widehat{f}(i)^2 = \Omega\!\left(\frac{\log^2 n}{n^2}\right) \tag{3} $$ for any monotone Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$, where $W^{(k)}[f] \stackrel{\rm def}{=} \sum_{S: \lvert S\rvert =k} \widehat{f}(S)^2$.

Now, consider two monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, and let $h\stackrel{\rm def}{=}fg$ be their parity. It is easy to see that we could have $W^{(0)}[h]+W^{(1)}[h]=0$, e.g. by considering $f,g$ to be two different dictator functions (but in that very specific case, $W^{(2)}[h]=1$). But must there be some non-negligible Fourier mass on the first 3 Fourier levels, then?

What can we say about $W^{(0)}[h]+W^{(1)}[h]+W^{(2)}[h] = \sum_{S: \lvert S\rvert \leq 2} \widehat{h}(S)^2$?

Conjecture 1. For any two monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, one must have $W^{(0)}[fg]+W^{(1)}[fg]+W^{(2)}[fg] > 0$.

Actually, I'd be actually inclined to believe the following stronger statement:

Conjecture 2. For any two monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, one must have $W^{(0)}[fg]+W^{(1)}[fg]+W^{(2)}[fg] \geq \frac{1}{\operatorname{poly}(n)}$.

Side note: this would have implications about weak learning of the class of "2-monotone" functions, which are exactly those functions obtained as parity or anti-parity of $2$ monotone functions. (See e.g. [BCOST15].) But more importantly, this is a very simple-looking question, that has been nagging at me for way too long.

[BCOST15] Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan. Learning Circuits with few Negations. APPROX-RANDOM 2015: 512-527

  • $\begingroup$ Can you shed some light on what arxiv.org/pdf/1705.04205.pdf means for this question? $\endgroup$
    – daniello
    May 14, 2017 at 10:29
  • $\begingroup$ @daniello As far as I can tell, not much, at least in terms of blackbox interpretation of the results. The question above would have applications to weak learning (learning to advantage $1/2+1/\mathrm{poly}(n)$), while the paper you link shows lower bound on testing (and a relaxation, parameterized testing). As far as I am aware, there is no direct connection between the two (the general connection is "(strong) learning implies testing"). $\endgroup$
    – Clement C.
    May 14, 2017 at 12:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.