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$
  • 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$ – Ryan O'Donnell May 24 at 14:14
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$
  • $\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 at 21:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.