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.

  • $\begingroup$ Have you already looked at these slides (specifically, the summary on slide 6) by Sushant Sachdeva? simons.berkeley.edu/sites/default/files/docs/568/… $\endgroup$
    – Clement C.
    May 12 at 23:19
  • $\begingroup$ 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. $\endgroup$
    – user6584
    May 14 at 1:19


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.

Browse other questions tagged or ask your own question.