1
$\begingroup$

Suppose $f$ and $g$ are Boolean functions without a constant term, and where every variable has the same influence. How to show every variable will have the same influence in $f \circ g$?

To me it seems like influence of a variable in $f \circ g$ is the product of influence of the outer variable in $f$ with the influence of the variable in $g$, but I'm not sure

$\endgroup$
4
  • $\begingroup$ Have you tried to prove your suspicion? $\endgroup$ Apr 25, 2022 at 17:25
  • $\begingroup$ Yes, but I'm not sure where I'm using the fact that the functions dont have a constant term in the polynomial representation $\endgroup$ Apr 25, 2022 at 17:44
  • 1
    $\begingroup$ You want a random input to $f \circ g$ to translate to a random input to $f$, which requires $g$ to be balanced. $\endgroup$ Apr 25, 2022 at 17:46
  • $\begingroup$ Sorry for the late reply but could you explain this in a little more detail? I just saw your answer and I'm still a little confused $\endgroup$ May 10, 2022 at 13:56

1 Answer 1

2
$\begingroup$

Suppose that $f\colon \{\pm1\}^n \to \{\pm1\}$ and that $g\colon \{\pm1\}^m \to \{\pm1\}$ is balanced. The composed function $f \circ g\colon \{\pm1\}^{nm} \to \{\pm1\}$ is given by $$ (f \circ g)(x) = f\bigl(g(x_{1,1},\ldots,x_{1,m}),\ldots g(x_{n,1},\ldots,x_{n,m})\bigr). $$ The influence of $x_{i,j}$ is the probability that if we sample $x \in \{\pm1\}^{nm}$ and construct $x'$ by flipping $x_{i,j}$ then $(f \circ g)(x) \neq (f \circ g)(x')$. This happens if:

  1. $g(x_{i,1},\ldots,x_{i,m}) \neq g(x'_{i,1},\ldots,x'_{i,m})$.
  2. $f(y_1,\ldots,y_n) \neq f(y'_1,\ldots,y'_n)$, where $y_i = g(x_{i,1},\ldots,x_{i,m})$ and $y'_i = g(x'_{i,1},\ldots,x'_{i,m})$.

The first property happens with probability $\operatorname{Inf}_j[g]$.

Since $g$ is balanced, the vector $(y_1,\ldots,y_n)$ is uniformly random. Therefore, given that the first property happens, the second property happens with probability $\operatorname{Inf}_i[f]$. In total, $$ \operatorname{Inf}_{i,j}[f \circ g] = \operatorname{Inf}_i[f] \operatorname{Inf}_j[g]. $$


Here is a calculational proof. Recall that $$ \operatorname{Inf}_i[f] = \sum_{i \in S} \hat{f}(S)^2. $$ The Fourier expansion of $f \circ g$ is $$ f \circ g = \sum_{S \subseteq [n]} \sum_{\substack{T_i \subseteq [m] \\ \text{for all } i \in S}} \hat{f}(S) \prod_{i \in S} \hat{g}(T_i) \prod_{i \in S} \prod_{j \in T_i} x_{i,j}. $$ Since $g$ is balanced, every monomial appears exactly once: $S$ needs to be the set of $i$ indices that appear in the monomial, and for each $i$, $T_i$ needs to be the set of $j$ indices such that $x_{i,j}$ appears in the monomial. (If $g$ were unbalanced, then $S$ could be any superset of the set of $i$ indices appearing in the monomial, with $T_i = \emptyset$ for any $i$ not appearing in the monomial.) Therefore \begin{align} \operatorname{Inf}_{i,j}[f \circ g] &= \sum_{i \in S} \sum_{\substack{T_k \, \forall k \in S \\ j \in T_i}} \hat{f}(S)^2 \prod_{k \in S} \hat{g}(T_k)^2 \\ &= \sum_{i \in S} \hat{f}(S)^2 \cdot \sum_{j \in T_i} \hat{g}(T_i)^2 \cdot \prod_{\substack{k \in S \\ k \neq i}} \sum_{T_k} \hat{g}(T_k)^2 \\ &= \sum_{i \in S} \hat{f}(S)^2 \cdot \operatorname{Inf}_j[g] \\ &= \operatorname{Inf}_i[f] \cdot \operatorname{Inf}_j[g], \end{align} using $$ \sum_T \hat{g}(T)^2 = 1, $$ since $g^2 = 1$.

$\endgroup$
4
  • $\begingroup$ Where can I read about that kind of function composition that you're assuming/defining? I'm only familiar with the normal one described for example here. $\endgroup$ May 10, 2022 at 17:37
  • $\begingroup$ It appears in the literature on query-to-communication lifting and in the literature on the KRW conjecture, for example. Here is a video lecture on lifting. $\endgroup$ May 10, 2022 at 17:48
  • $\begingroup$ Hmm, I can't find the string "lift" in Wikipedia's function composition article. I only skimmed a bit of the video, but he first uses "$\circ$" after 8 minutes in $f \circ g^n$. Are you sure you're not talking about that, instead of about $f \circ g$? $\endgroup$ May 10, 2022 at 18:24
  • $\begingroup$ It's the same thing. The notation $f \circ g^n$ is more pedantic. $\endgroup$ May 10, 2022 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.