On some extensions of the FKN theorem

by Jacek Jendrej, Krzysztof Oleszkiewicz, and Jakub O. Wojtaszczyk

Theory of Computing, Volume 11(18), pp. 445-469, 2015

Bibliography with links to cited articles

[1]   William Beckner: Inequalities in Fourier analysis. Ann. of Math., 102(1):159–182, 1975. [doi:10.2307/1970980]

[2]   Aline Bonami: Étude des coefficients Fourier des fonctions de Lp(G). Ann. Inst. Fourier, 20(2):335–402, 1970. EuDML.

[3]   Irit Dinur: The PCP theorem by gap amplification. J. ACM, 54(3:12), 2007. Preliminary versions in STOC’06 and ECCC. [doi:10.1145/1236457.1236459]

[4]   Ehud Friedgut, Gil Kalai, and Assaf Naor: Boolean functions whose Fourier transform is concentrated on the first two levels. Adv. in Appl. Math., 29(3):427–437, 2002. [doi:10.1016/S0196-8858(02)00024-6]

[5]   Guy Kindler: Property Testing, PCP and Juntas. Ph. D. thesis, Tel Aviv University, 2002. Available at author’s website.

[6]   Guy Kindler and Shmuel Safra: Noise-resistant Boolean functions are juntas. Preprint, 2002. Available at author’s website.

[7]   Hermann König, Carsten Schütt, and Nicole Tomczak-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]

[8]   Rafał Latała and Krzysztof Oleszkiewicz: On the best constant in the Khinchin-Kahane inequality. Studia Math., 109(1):101–104, 1994. EuDML.

[9]   Józef Marcinkiewicz and Antoni Zygmund: Sur les fonctions indépendantes. Fund. Math., 29(1):60–90, 1937. EuDML.

[10]   Piotr Nayar: FKN theorem on the biased cube. Colloq. Math., 137(2):253–261, 2014. [doi:10.4064/cm137-2-9, arXiv:1311.3179]

[11]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge University Press, 2014.

[12]   Krzysztof Oleszkiewicz: 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]

[13]   Aviad Rubinstein: 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.

[14]   Aviad Rubinstein and Muli Safra: Boolean functions whose Fourier transform is concentrated on pairwise disjoint subsets of the input, 2015. [arXiv:1512.09045]

[15]   Walter Rudin: Functional Analysis. McGraw-Hill, Inc., New York, 2nd edition, 1991.

[16]   Stanisław J. Szarek: On the best constants in the Khinchin inequality. Studia Math., 58(2):197–208, 1976. EuDML.