# Influence of a variable in composition of Boolean functions

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

• Have you tried to prove your suspicion? Apr 25, 2022 at 17:25
• Yes, but I'm not sure where I'm using the fact that the functions dont have a constant term in the polynomial representation Apr 25, 2022 at 17:44
• You want a random input to $f \circ g$ to translate to a random input to $f$, which requires $g$ to be balanced. Apr 25, 2022 at 17:46
• 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 May 10, 2022 at 13:56

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

• 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. May 10, 2022 at 17:37
• 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. May 10, 2022 at 17:48
• 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$? May 10, 2022 at 18:24
• It's the same thing. The notation $f \circ g^n$ is more pedantic. May 10, 2022 at 18:25