On some extensions of the FKN theorem
Received: January 19, 2013
Revised: September 19, 2015
Published: December 29, 2015
Revised: September 19, 2015
Published: December 29, 2015
Keywords: independent random variables, Rademacher variables, absolute value variation, Fourier expansion, Irit Dinur PCP proof
Categories: complexity theory, Fourier analysis, Rademacher variables, absolute value variation, PCP, special issue, Boolean special issue
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.