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]