# Which (almost) balanced Boolean function has smallest “total” influence

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.

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?
• 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 May 24 '19 at 14:14

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}$$