pdf icon
On some extensions of the FKN theorem
Received: January 19, 2013
Revised: September 19, 2015
Published: December 29, 2015
Download article from ToC site:
[PDF (295K)] [PS (1630K)] [Source ZIP]
Keywords: independent random variables, Rademacher variables, absolute value variation, Fourier expansion, Irit Dinur PCP proof
ACM Classification: F.2.2, F.1.3, G.1.6
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40

Abstract: [Plain Text Version]

$ \newcommand{\Var}{{\mathrm {Var}}} $

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.