On the Converse of Talagrand's Influence Inequality

2015/06/21 by Saleet Klein, Amit Levi, Klein, Saleet +7
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Inequalities and Applications #Mathematics and Applications #Point processes and geometric inequalities #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1506.06325

openalex publication_date 2015/06/21 · arxiv created 2015/06/23 · arxiv updated 2015/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 numbers 0<a₁,a₂,…,a_n≤ 1 such that ∑_j=1ⁿ a_j/(1-log a_j)≥ C for some constant C>0, it is possible to find a roughly balanced Boolean function f such that \textrmInf_j[f] < a_j for every 1 ≤ j ≤ n.

Related

• Talagrand inequality at second order and application to Boolean analysis
• KKL theorem for the influence of a set of variables
• A Counterexample to a Directed KKL Inequality
• Influences in Product Spaces: KKL and BKKKL Revisited
• The Courtade-Kumar Most Informative Boolean Function Conjecture and a\n Symmetrized Li-M 'edard Conjecture are Equivalent