An entropic proof of Chang's inequality

DOI10.1137/120877982MaRDI QIDQ4979832zbMATH OpenOpenAlexFDO

Authors Russell Impagliazzo, Cristopher Moore, Alexander Russell

Publication date 19 June 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.0263

zbMATH Keywords

Boolean functionsChang's lemmaFourier analysis

Mathematics Subject Classification ID

Arithmetic combinatorics; higher degree uniformity (11B30) Fourier series and coefficients in several variables (42B05)

Abstract: Chang's lemma is a useful tool in additive combinatorics and the analysis of Boolean functions. Here we give an elementary proof using entropy. The constant we obtain is tight, and we give a slight improvement in the case where the variables are highly biased.

Recommendations

• Chang's lemma via Pinsker's inequality
• Covering the large spectrum and generalized Riesz products
• Proof of a hypercontractive estimate via entropy
• Entropy and concentration
• scientific article; zbMATH DE number 6351506

Cited in

(11)

• Chvátal's conjecture and correlation inequalities
• An elementary analog of the operator method in additive combinatorics
• Chang's lemma via Pinsker's inequality
• Finite field models in arithmetic combinatorics -- ten years on
• Fooling Polytopes
• Two new results about quantum exact learning
• Fourier bounds and pseudorandom generators for product tests
• Biased halfspaces, noise sensitivity, and local Chernoff inequalities
• Covering the large spectrum and generalized Riesz products
• An Explicit Croot-Łaba-Sisask Lemma Free of Probabilistic Language
• Comparing computational entropies below majority (or: when is the dense model theorem false?)

This page was built for publication: An entropic proof of Chang's inequality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4979832)