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:
- 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.
- 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:
- What is a lower bound on total influence (as opposed to maximum influence) of Boolean functions where each coordinate $i \in [n]$ is influential?
- Which almost balanced Boolean function, whose every coordinate has non-zero influence has the smallest total influence?