Kahn–Kalai–Linial inequality

• Sub-additivity of entropy for Bernoulli product measures
• The KKL inequality: statement and elementary bounds
• Walsh–Fourier analysis on the uniform cube and the KKL reduction
• Hypercontractivity bounds for indicator functions
• Hypercontractivity applied to discrete derivatives
• Log-sum estimates for damped influences under p-biased measures
• The edge-isoperimetric inequality and the logarithmic KKL reduction
• The KKL inequality on the uniform cube with constant 2
• A damped KKL inequality under p-biased measures
• The KKL inequality at p = 1/2, and the p-biased basis at p = 1/2
• The KKL inequality for events, and sharp thresholds
• The KKL inequality under p-biased measures: reflection and threshold consequences
• Decomposition of the variance by maximal element
• The capped estimate in the hypercontractive range
• The capped estimate from convexity
• The capped estimate in the hypercontractive range with a gap condition
• Degree truncation of the capped estimate under p-biased measures

TheoremKKL inequality for p-biased measures#●ready to prove

KKL inequality for p-biased measures (Bourgain–Kahn–Kalai–Katznelson–Linial; Talagrand). For every p ∈ (0, 1) there is c > 0 such that for every finite nonempty E and every Boolean function φ on {0, 1}^E, c · Var_p(φ) · log (1 / maxₑ Infₑ^p(φ)) ≤ ∑ₑ Infₑ^p(φ), where Infₑ^p(φ) is the probability under the Bernoulli(p) product measure that e is pivotal for φ.

Talagrand's inequality Var_p(φ) ≤ K(p) ∑ₑ Infₑ / log (1 / (p (1 - p) Infₑ)) gives this with c = 1 / K(p), since each Infₑ ≤ maxₑ Infₑ.

public theorem_wanted kkl_pbiased :
    ∀ p : ℝ, 0 < p → p < 1 → ∃ c : ℝ, 0 < c ∧ KKLHypercontractive p c

Sources

• M. Talagrand, On Russo's approximate zero-one law, Ann. Probab. 22 (1994); J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson, N. Linial, The influence of variables in product spaces, Israel J. Math. 77 (1992).

Uses 1

Statement usesKKL inequality with constant \(c\) for the \(p\)-biased measure

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.