On the Converse of Talagrand's Influence Inequality

Saleet Klein, Amit Levi, Muli Safra +2

In 1994, Talagrand showed a generalization of the celebrated KKL theorem. In this work, we prove that the converse of this generalization also holds. Namely, for any sequence of nu…