4
$\begingroup$

The Kahn–Kalai–Linial (KKL) Theorem says that for any balanced Boolean function $f:\{−1,1\}^n→\{−1,1\}$ we have $\max_i {\bf Inf}_i(f) = \Omega\left(\frac{\log n}{n}\right)$. I am looking for a concrete version of this theorem that holds for all $n$. What is the tightest concrete version known?

$\endgroup$
2
  • 3
    $\begingroup$ I mean, the bound $\Omega\left(\frac{\log n}{n}\right)$ does hold for all $n$, provided the implicit constant is small enough. Can't you just work through a proof of the KKL theorem and keep track of the constant? It might be a pain, but should be straightforward. $\endgroup$ Commented May 11, 2023 at 16:07
  • 1
    $\begingroup$ Yes, that is certainly possible, but I suspect this is already well-known in the literature and if so I would like to cite it (and avoid repeating work!) $\endgroup$
    – user6584
    Commented May 11, 2023 at 17:33

1 Answer 1

5
$\begingroup$

See Exercise 9.30 of Ryan O'Donnell's Analysis of Boolean Functions book [1]: for any $f\colon\{-1,1\}^n\to \{-1,1\}$, $$ \mathbf{MaxInf}[f]\geq \frac{1}{2}\mathbf{Var}[f]\cdot \frac{\ln n}{n} (1-o(1)) $$ and what's in the $o(1)$ should be easy to figure out from the subquestion (b) of the exercise.

[1] O'Donnell, R. (2014). Analysis of Boolean Functions. Cambridge: Cambridge University Press. doi:10.1017/CBO9781139814782. See also arXiv:2105.10386.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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