# Influence for boolean functions on larger domains

Most of the literature on boolean function complexity considers boolean functions on $$\{0,1\}^n$$, but I am not finding very much about functions over larger (finite) domains. Specifically, fix a balanced function $$f: S^n \rightarrow \{0,1\}$$ where for concreteness we let $$S=\{0,1\}^\ell$$. There are multiple ways one could imagine defining influence for such a function, but I am interested in either of the following possibilities:

• $${\bf Inf}^1_i(f) = \Pr_{x_1, \ldots, x_n, x'_i \in S}[f(x_1, \ldots, x_i, \ldots, x_n) \neq f(x_1, \ldots, x'_i, \ldots, x_n)]$$, i.e., this is the probability that randomly resampling the $$i$$th "block" of input (while keeping the rest fixed) changes the value of $$f$$.
• $${\bf Inf}^2_i(f) = \Pr_{x_1, \ldots, x_n \in S}[\exists j \in [\ell] : f(x_1, \ldots, x_i, \ldots, x_n) \neq f(x_1, \ldots, x_i \oplus e_j, \ldots, x_n)]$$, where $$e_j \in \{0,1\}^\ell$$ is the vector that is 1 in the $$j$$th position and 0 elsewhere. This is the probability that there is a "small perturbation" of the $$i$$th block that changes the value of $$f$$.

Letting $${\bf Inf}^1(f) = \max_i \{{\bf Inf}_i^1(f)\}$$ and analogously for $${\bf Inf}^2(f)$$, I am looking lower bounds on $${\bf Inf}^1(f), {\bf Inf}^2(f)$$ that hold for all $$f$$. Note that a trivial bound can be obtained by viewing $$f$$ as a function $$f:\{0,1\}^{n\ell} \rightarrow \{0,1\}$$ -- for example, the KKL theorem immediately implies that $${\bf Inf}^2(f) = \Omega\left(\frac{\log n\ell}{n\ell}\right)$$ -- but I am looking for something stronger.

I note also that this is clearly connected to one-round collective coin-flipping protocols, but I have not found any better bounds in that literature, either.

• Have you already looked at these slides (specifically, the summary on slide 6) by Sushant Sachdeva? simons.berkeley.edu/sites/default/files/docs/568/… May 12 at 23:19
• Thanks for the pointer. I did look at those slides, and the Mossel paper as well (which seemed like the most relevant reference). Unfortunately, that paper seemed to focus on a more-general problem and I found it very difficult to get a clear take-away message from it for my particular problem. May 14 at 1:19