Theory of Computing
-------------------
Title : On some extensions of the FKN theorem
Authors : Jacek Jendrej, Krzysztof Oleszkiewicz, and Jakub O. Wojtaszczyk
Volume : 11
Number : 18
Pages : 445-469
URL : http://www.theoryofcomputing.org/articles/v011a018
Abstract
--------
Let $S=a_{1}r_{1}+a_{2}r_{2}+\ldots+a_{n}r_{n}$ be a weighted Rademacher
sum. Friedgut, Kalai, and Naor have shown that if $\Var(|S|)$ is much
smaller than $\Var(S)$, then the sum is largely determined by one of
the summands. We provide a simple and elementary proof of this result,
strengthen it, and extend it in various ways to a more general
setting.