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.
