# Concrete version of KKL Theorem

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?

• 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. May 11 at 16:07
• 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!) May 11 at 17:33

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.