An Entropic Proof of Chang's Inequality
Authors:
- Russell ImpagliazzoRIRussell Impagliazzo
- Cristopher MooreCMCristopher Moore
- Alexander RussellARAlexander Russell
- 1 January 2014
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 28 (1) , 173-176
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. We obtain a tight constant and give a slight improvement in the case where the variables are highly biased.Keywords
All Related Versions
This publication has 2 references indexed in Scilit:
- A polynomial bound in Freiman's theoremDuke Mathematical Journal, 2002
- How much are increasing sets positively correlated?Combinatorica, 1996