4
$\begingroup$

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?
$\endgroup$
1
  • 4
    $\begingroup$ 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) $\endgroup$ May 24, 2019 at 14:14

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Clement C.
    May 28, 2019 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy