<p>You have the lower bound of <span class="math-container">$\mathbf{Inf}[f] \geq \operatorname{Var}[ f ]$</span> for <span class="math-container">$f\colon  \{-1,1\}^n\to\mathbb{R}$</span> (Poincaré Inequality), so that for an (almost) balanced <span class="math-container">$f\colon  \{-1,1\}^n\to\{-1,1\}$</span> one must have
<span class="math-container">$$
\mathbf{Inf}[f] \gtrsim 1 \tag{1}
$$</span>
(say, <span class="math-container">$1-\epsilon$</span>, depending on the near-unbalanced assumption). Further, for a dictator function, this is tight:
<span class="math-container">$$
\mathbf{Inf}[\chi_1] = \mathbf{Inf}_1[\chi_1] = 1\,. \tag{2}
$$</span></p>

CC BY-SA 4.0
2019-05-28T21:31:23.730Z
After the edit: the same bounds hold for the "all-variables must have positive influence" case. (1) of course still holds; as for (2), following Ryan's comment, just modify the dictator function at a single point to get a similar statement.
Clement C.
CC BY-SA 4.0
2019-05-16T22:39:47.647Z
2019-05-16T22:39:47.647Z
Clement C.
<p>The well known <strong><em>Kahn–Kalai–Linial (KKL) Theorem</em></strong> says that for any Boolean function <span class="math-container">$f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$</span>
<span class="math-container">$$
\max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot \Omega\Bigl(\frac{\log n}{n}\Bigr).
$$</span>
The lower bound on maximum influence is achieved by the <span class="math-container">$\mathsf{Tribes}_n$</span> function. I have two questions in this regard:</p>

<ol>
<li>What is a lower bound on <strong>total</strong> influence (as opposed to maximum influence) of Boolean functions? For a meaningful answer, it is necessary to consider functions that are (almost) balanced like <span class="math-container">$\mathsf{Tribes}_n$</span>. For instance, a constant function has <span class="math-container">$0$</span> total influence.</li>
<li>Which almost balanced Boolean function achieves the lower bound on total influence? i.e., which balanced function has the smallest total influence? This question is a natural follow-up to the first question.</li>
</ol>

<p>Thanks in advance!</p>

<hr>

<p><strong>Edit:</strong></p>

<p>As Clement C. pointed out, there is a simple solution to the question for the Dictator function. Perhaps more interesting is to have the constraint that all variables <span class="math-container">$x_1, \dots , x_n$</span> have non-zero influence.</p>

<p>Questions:</p>

<ol>
<li>What is a lower bound on <strong>total</strong> influence (as opposed to maximum influence) of Boolean functions <strong><em>where each coordinate <span class="math-container">$i \in [n]$</span> is influential</em></strong>? </li>
<li>Which almost balanced Boolean function, <strong><em>whose every coordinate has non-zero influence</em></strong> has the smallest total influence?</li>
</ol>

CC BY-SA 4.0
2019-05-24T14:14:50.760Z
To give every coordinate nonzero influence while changing the total influence by a negligible amount, just change the Dictator's value at one point. E.g. f(x) = x1 and not (x2 and...and xn)
Ryan O'Donnell
<cc.complexity-theory><co.combinatorics><boolean-functions><fourier-analysis><extremal-combinatorics>
Which (almost) balanced Boolean function has smallest "total" influence
user52879
# Which (almost) balanced Boolean function has smallest "total" influence

(Asked by: username_0 on 2019-05-16)

The well known ***Kahn–Kalai–Linial (KKL) Theorem*** says that for any Boolean function $f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$
$$
\max\_{i \in [n]} \{\mathbf{Inf}\_i[f] \} \geq \mathop{\bf Var}[f] \cdot \Omega\Bigl(\frac{\log n}{n}\Bigr).
$$
The lower bound on maximum influence is achieved by the $\mathsf{Tribes}\_n$ function. I have two questions in this regard:

1. What is a lower bound on **total** influence (as opposed to maximum influence) of Boolean functions? For a meaningful answer, it is necessary to consider functions that are (almost) balanced like $\mathsf{Tribes}\_n$. For instance, a constant function has $0$ total influence.
2. Which almost balanced Boolean function achieves the lower bound on total influence? i.e., which balanced function has the smallest total influence? This question is a natural follow-up to the first question.

Thanks in advance!

---

**Edit:**

As Clement C. pointed out, there is a simple solution to the question for the Dictator function. Perhaps more interesting is to have the constraint that all variables $x\_1, \dots , x\_n$ have non-zero influence.

Questions:

1. What is a lower bound on **total** influence (as opposed to maximum influence) of Boolean functions ***where each coordinate $i \in [n]$ is influential***?
2. Which almost balanced Boolean function, ***whose every coordinate has non-zero influence*** has the smallest total influence?

**Tags:** cc.complexity-theory, co.combinatorics, boolean-functions, fourier-analysis, extremal-combinatorics
> **Comments:**
> **username_1**: To give every coordinate nonzero influence while changing the total influence by a negligible amount, just change the Dictator's value at one point. E.g. f(x) = x1 and not (x2 and...and xn)  

---

## 1 answers

### Answer by username_2 on 2019-05-16. Score: 2

You have the lower bound of $\mathbf{Inf}[f] \geq \operatorname{Var}[ f ]$ for $f\colon \{-1,1\}^n\to\mathbb{R}$ (Poincaré Inequality), so that for an (almost) balanced $f\colon \{-1,1\}^n\to\{-1,1\}$ one must have
$$
\mathbf{Inf}[f] \gtrsim 1 \tag{1}
$$
(say, $1-\epsilon$, depending on the near-unbalanced assumption). Further, for a dictator function, this is tight:
$$
\mathbf{Inf}[\chi\_1] = \mathbf{Inf}\_1[\chi\_1] = 1\,. \tag{2}
$$

> **Comments:**
> **username_2**: After the edit: the same bounds hold for the "all-variables must have positive influence" case. (1) of course still holds; as for (2), following Ryan's comment, just modify the dictator function at a single point to get a similar statement.  

---

