<p>Most of the literature on boolean function complexity considers boolean functions on <span class="math-container">$\{0,1\}^n$</span>, but I am not finding very much about functions over larger (finite) domains. Specifically, fix a balanced function <span class="math-container">$f: S^n \rightarrow \{0,1\}$</span> where for concreteness we let <span class="math-container">$S=\{0,1\}^\ell$</span>. There are multiple ways one could imagine defining influence for such a function, but I am interested in either of the following possibilities:</p>
<ul>
<li><span class="math-container">${\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)]$</span>, i.e., this is the probability that randomly resampling the <span class="math-container">$i$</span>th &quot;block&quot; of input (while keeping the rest fixed) changes the value of <span class="math-container">$f$</span>.</li>
<li><span class="math-container">${\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)]$</span>, where <span class="math-container">$e_j \in \{0,1\}^\ell$</span> is the vector that is 1 in the <span class="math-container">$j$</span>th position and 0 elsewhere. This is the probability that there is a &quot;small perturbation&quot; of the <span class="math-container">$i$</span>th block that changes the value of <span class="math-container">$f$</span>.</li>
</ul>
<p>Letting <span class="math-container">${\bf Inf}^1(f) = \max_i \{{\bf Inf}_i^1(f)\}$</span> and analogously for <span class="math-container">${\bf Inf}^2(f)$</span>, I am looking lower bounds on <span class="math-container">${\bf Inf}^1(f), {\bf Inf}^2(f)$</span> that hold for all <span class="math-container">$f$</span>. Note that a trivial bound can be obtained by viewing <span class="math-container">$f$</span> as a function <span class="math-container">$f:\{0,1\}^{n\ell} \rightarrow \{0,1\}$</span> -- for example, the KKL theorem immediately implies that <span class="math-container">${\bf Inf}^2(f) = \Omega\left(\frac{\log n\ell}{n\ell}\right)$</span> -- but I am looking for something stronger.</p>
<p>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.</p>

CC BY-SA 4.0
2023-05-12T23:19:42.700Z
Have you already looked at these slides (specifically, the summary on slide 6) by Sushant Sachdeva? https://simons.berkeley.edu/sites/default/files/docs/568/sachdevaslides.pdf
Clement C.
CC BY-SA 4.0
2023-05-14T01:19:10.297Z
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.
user6584
<co.combinatorics><boolean-functions>
Influence for boolean functions on larger domains
user6584
# Influence for boolean functions on larger domains

(Asked by: username_0 on 2023-05-11)

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.

**Tags:** co.combinatorics, boolean-functions

> **Comments:**
> **username_1**: Have you already looked at these slides (specifically, the summary on slide 6) by Sushant Sachdeva? https://simons.berkeley.edu/sites/default/files/docs/568/sachdevaslides.pdf  
> **username_0**: 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.  

---

## 0 answers

