zbMATH — the first resource for mathematics

On some extensions of the FKN theorem. (English) Zbl 1352.60029
Summary: Let \(S=a_{1}r_{1}+a_{2}r_{2}+\cdots +a_{n}r_{n}\) be a weighted Rademacher sum. E. Friedgut et al. [Adv. Appl. Math. 29, No. 3, 427–437 (2002; Zbl 1039.91014)] have shown that if \(\operatorname{Var}(|S|)\) is much smaller than \(\operatorname{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.

60E15 Inequalities; stochastic orderings
42C10 Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.)
Zbl 1039.91014
Full Text: DOI
[1] [1] WILLIAMBECKNER: Inequalities in Fourier analysis. Ann. of Math., 102(1):159–182, 1975. [doi:10.2307/1970980]446,457
[2] [2] ALINEBONAMI: Étude des coefficients Fourier des fonctions de Lp(G). Ann. Inst. Fourier, 20(2):335–402, 1970.EuDML.446,457
[3] [3] IRITDINUR: The PCP theorem by gap amplification. J. ACM, 54(3:12), 2007. Preliminary versions inSTOC’06andECCC. [doi:10.1145/1236457.1236459]446
[4] [4] EHUDFRIEDGUT, GILKALAI,ANDASSAFNAOR: Boolean functions whose Fourier transform is concentrated on the first two levels. Adv. in Appl. Math., 29(3):427–437, 2002. [doi:10.1016/S01968858(02)00024-6]446,455,458
[5] [5] GUYKINDLER: Property Testing, PCP and Juntas. Ph. D. thesis, Tel Aviv University, 2002. Available atauthor’s website.446,458,460
[6] [6] GUYKINDLER ANDSHMUELSAFRA: Noise-resistant Boolean functions are juntas. Preprint, 2002. Available atauthor’s website.446,458,460
[7] [7] HERMANNKÖNIG, CARSTENSCHÜTT,ANDNICOLETOMCZAK-JAEGERMANN: Projection constants of symmetric spaces and variants of Khintchine’s inequality. J. Reine Angew. Math., 1999(511):1–42, 1999. [doi:10.1515/crll.1999.511.1]446 · Zbl 0926.46008
[8] [8] RAFAŁLATAŁA ANDKRZYSZTOFOLESZKIEWICZ: On the best constant in the Khinchin-Kahane inequality. Studia Math., 109(1):101–104, 1994.EuDML.450
[9] [9] JÓZEFMARCINKIEWICZ ANDANTONIZYGMUND: Sur les fonctions indépendantes. Fund. Math., 29(1):60–90, 1937.EuDML.450
[10] [10] PIOTRNAYAR: FKN theorem on the biased cube.Colloq. Math., 137(2):253–261, 2014. [doi:10.4064/cm137-2-9,arXiv:1311.3179]460,461
[11] [11] RYANO’DONNELL: Analysis of Boolean Functions. Cambridge University Press, 2014.447
[12] [12] KRZYSZTOFOLESZKIEWICZ: On a nonsymmetric version of the Khinchine-Kahane inequality. In Stochastic Inequalities and Applications, volume 56 of Progress in Probability, pp. 157–168. Springer/Birkhäuser, 2003. [doi:10.1007/978-3-0348-8069-5_11]460 THEORY OFCOMPUTING, Volume 11 (18), 2015, pp. 445–469467 JACEKJENDREJ, KRZYSZTOFOLESZKIEWICZ ANDJAKUBO. WOJTASZCZYK
[13] [13] AVIADRUBINSTEIN: Boolean functions whose Fourier transform is concentrated on pair-wise disjoint subsets of the inputs. Master’s thesis.School of Computer Science, Tel-Aviv University, October 2012.465,466
[14] [14] AVIADRUBINSTEIN ANDMULISAFRA: Boolean functions whose Fourier transform is concentrated on pairwise disjoint subsets of the input, 2015. [arXiv:1512.09045]465
[15] [15] WALTERRUDIN: Functional Analysis. McGraw-Hill, Inc., New York, 2nd edition, 1991.447
[16] [16] STANISŁAWJ. SZAREK: On the best constants in the Khinchin inequality. Studia Math., 58(2):197– 208, 1976.EuDML.450
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.