Hypercontractivity Via the Entropy Method

by Eric Blais and Li-Yang Tan

Theory of Computing, Volume 9(29), pp. 889-896, 2013

Bibliography with links to cited articles

[1]   Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou: Hypercontractivity, sum-of-squares proofs, and their applications. In Proc. 44th STOC, pp. 307–326. ACM Press, 2012. [doi:10.1145/2213977.2214006]

[2]   Michael Ben-Or and Nathan Linial: Collective coin flipping. In Silvio Micali and Franco Preparata, editors, Randomness and Computation, volume 5 of Advances in Computing Research: A research annual, pp. 91–115. JAI Press, 1989. Preliminary version in FOCS’85.

[3]   Aline Bonami: Ensembles Λ(p) dans le dual de D. Annales de l’Institut Fourier, 18(2):193–204, 1968. EuDML.

[4]   Aline Bonami: Étude des coefficients Fourier des fonctions de Lp(G). Annales de l’Institut Fourier, 20(2):335–402, 1970. EuDML.

[5]   Jean Bourgain: On the distribution of the Fourier spectrum of Boolean functions. Israel J. Math., 131(1):269–276, 2002. [doi:10.1007/BF02785861]

[6]   Jean Bourgain, Jeff Kahn, Gil Kalai, Yitzhak Katznelson, and Nathan Linial: The influence of variables in product spaces. Israel J. Math., 77(1-2):55–64, 1992. [doi:10.1007/BF02808010]

[7]   Thomas M. Cover and Joy A. Thomas: Elements of Information Theory. Wiley, 1991.

[8]   Uriel Feige and Joe Kilian: Zero knowledge and the chromatic number. J. Comput. System Sci., 57(2):187–199, 1998. Preliminary version in CCC’96. [doi:10.1006/jcss.1998.1587]

[9]   Ehud Friedgut: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27–35, 1998. [doi:10.1007/PL00009809]

[10]   Ehud Friedgut: Sharp thresholds of graph properties, and the k-SAT problem. J. Amer. Math. Soc., 12(4):1017–1054, 1999. AMS.

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

[12]   Ehud Friedgut and Vojtech Rödl: Proof of a hypercontractive estimate via entropy. Israel J. Math., 125(1):369–380, 2001. [doi:10.1007/BF02773387]

[13]   Christophe Garban, Gábor Pete, and Oded Schramm: The Fourier spectrum of critical percolation. Acta Mathematica, 205(1):19–104, 2010. [doi:10.1007/s11511-010-0051-x]

[14]   Leonard Gross: Logarithmic Sobolev inequalities. American Journal of Mathematics, 97(4):1061–1083, 1975. JSTOR.

[15]   Jeff Kahn, Gil Kalai, and Nathan Linial: The influence of variables on boolean functions (extended abstract). In Proc. 29th FOCS, pp. 68–80. IEEE Comp. Soc. Press, 1988. [doi:10.1109/SFCS.1988.21923]

[16]   Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, and Yuan Zhou: Hypercontractivity inequalities via SOS, and the Frankl-Rödl graph. Technical report, 2012. To appear in SODA’14. [arXiv:1212.5324]

[17]   Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007. Preliminary version in FOCS’04. See also at ECCC. [doi:10.1137/S0097539705447372]

[18]   Subhash Khot and Nisheeth K. Vishnoi: The Unique Games Conjecture, integrality gap for cut problems and embeddability of negative type metrics into 1. In Proc. 46th FOCS, pp. 53–62. IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.74]

[19]   Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz: Noise stability of functions with low influences: invariance and optimality. Ann. of Math., 171(1):295–341, 2010. Preliminary version in FOCS’05. [doi:10.4007/annals.2010.171.295]

[20]   Ryan O’Donnell: The Analysis of Boolean Functions. Cambridge Univ. Press, 2014, to appear. Preliminary version at analysisofbooleanfunctions.org.

[21]   Ryan O’Donnell and Rocco A. Servedio: Learning monotone decision trees in polynomial time. SIAM J. Comput., 37(3):827–844, 2007. Preliminary version in CCC’06. [doi:10.1137/060669309]

[22]   Michel Talagrand: On Russo’s approximate zero-one law. Ann. Probab., 22(3):1576–1587, 1994. JSTOR.

[23]   Ronald de Wolf: A Brief Introduction to Fourier Analysis on the Boolean Cube. Number 1 in Graduate Surveys. Theory of Computing Library, 2008. [doi:10.4086/toc.gs.2008.001]