<p>See Exercise 9.30 of Ryan O'Donnell's <em>Analysis of Boolean Functions</em> book [1]: for any <span class="math-container">$f\colon\{-1,1\}^n\to \{-1,1\}$</span>,
<span class="math-container">$$
\mathbf{MaxInf}[f]\geq \frac{1}{2}\mathbf{Var}[f]\cdot \frac{\ln n}{n} (1-o(1))
$$</span>
and what's in the <span class="math-container">$o(1)$</span> should be easy to figure out from the subquestion (b) of the exercise.</p>
<p>[1] O'Donnell, R. (2014). <em>Analysis of Boolean Functions</em>. Cambridge: Cambridge University Press. doi:10.1017/CBO9781139814782. See also <a href="https://arxiv.org/abs/2105.10386" rel="noreferrer">arXiv:2105.10386</a>.</p>

CC BY-SA 4.0
2023-05-13T22:17:28.890Z
2023-05-13T22:17:28.890Z
Clement C.
<p>The Kahn–Kalai–Linial (KKL) Theorem says that for any balanced Boolean function <span class="math-container">$f:\{−1,1\}^n→\{−1,1\}$</span> we have <span class="math-container">$\max_i {\bf Inf}_i(f) = \Omega\left(\frac{\log n}{n}\right)$</span>. I am looking for a concrete version of this theorem that holds for all <span class="math-container">$n$</span>. What is the tightest concrete version known?</p>

CC BY-SA 4.0
2023-05-11T16:07:39.717Z
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.
mathworker21
CC BY-SA 4.0
2023-05-11T17:33:35.270Z
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!)
user6584
<boolean-functions><combinatorics><extremal-combinatorics>
Concrete version of KKL Theorem
user6584
# Concrete version of KKL Theorem

(Asked by: username_0 on 2023-05-10)

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?

**Tags:** boolean-functions, combinatorics, extremal-combinatorics
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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!)  

---

## 1 answers

### Answer by username_2 on 2023-05-13. Score: 5

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](https://arxiv.org/abs/2105.10386).


---

