Problems / probability-statistics
probability-statistics / Analysis of Boolean functions
Talagrand’s convolution conjecture
On the Boolean hypercube $G = \{-1,1\}^n$ with uniform measure $\lambda$, let $T_\mu f(x) = \int_G f(x \odot y)\,d\mu(y)$ be convolution by a finite positive measure $\mu$, and set
$$\psi_\mu(u) = \sup\{u\,\lambda(\{T_\mu f \ge u\}) : f \ge 0,\ \|f\|_1 = 1\},$$
which measures how much better than Markov's inequality convolution makes the tail. In 1989 Talagrand conjectured that for the biased-coin product measure $\mu_a = (\tfrac{1+a}{2}\delta_1 + \tfrac{1-a}{2}\delta_{-1})^{\otimes n}$ with $0 < a < 1$,
$$\psi_{\mu_a}(u) \le \frac{C_a}{\sqrt{\log u}} \qquad (u > 1),$$
with $C_a$ depending on $a$ alone and not on the dimension $n$. He offered a \$1000 prize for a proof. The Gaussian analogue was settled by Eldan and Lee; the hypercube case, the original, stayed open.
This paper claims the conjectured bound.