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?
$\begingroup$
$\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$– mathworker21May 11 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$– user6584May 11 at 17:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
