Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
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.