Noise Stability is Computable and Approximately Low-Dimensional

by Anindya De, Elchanan Mossel, and Joe Neeman

Theory of Computing, Volume 15(6), pp. 1-47, 2019

Bibliography with links to cited articles

[1]   Dominique Bakry and Michel Ledoux: Lévy–Gromov’s isoperimetric inequality for an infinite dimensional diffusion generator. Inventiones Math., 123(1):259–281, 1996. [doi:10.1007/BF01232376]

[2]   Itai Benjamini, Gil Kalai, and Oded Schramm: Noise sensitivity of Boolean functions and applications to percolation. Publ. Math. Inst. Hautes Études Sci., 90:5–43, 1999. [doi:10.1007/BF02698830, arXiv:math/9811157]

[3]   Christer Borell: Geometric bounds on the Ornstein-Uhlenbeck velocity process. Zeitschrift für Wahrscheinlichkeitstheorie und Verw. Gebiete, 70(1):1–13, 1985. [doi:10.1007/BF00532234]

[4]   Anthony Carbery and James Wright: Distributional and Lq norm inequalities for polynomials over convex bodies in Rn. Mathematical Research Letters, 8(3):233–248, 2001. [doi:10.4310/MRL.2001.v8.n3.a1]

[5]   Joe Corneli, Ivan Corwin, Stephanie Hurder, Vojislam Sesum, Ya Xu, Elizabeth Adams, Diana Davis, Michelle Lee, Regina Visocchi, Neil Hoffman, and Robert Hardt: Double bubbles in Gauss space and spheres. Houston J. Math., 34(1):181–204, 2008.

[6]   Anindya De, Elchanan Mossel, and Joe Neeman: Majority is stablest: Discrete and SoS. Theory of Computing, 12(4):1–50, 2016. Preliminary version in STOC’13. [doi:10.4086/toc.2016.v012a004, arXiv:1211.1001]

[7]   Anindya De, Elchanan Mossel, and Joe Neeman: Noise stability is computable and approximately low-dimensional. In Proc. 32nd Computational Complexity Conf. (CCC’17), pp. 10:1–10:11. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. (conference version of this paper). [doi:10.4230/LIPIcs.CCC.2017.10, arXiv:1701.01483]

[8]   Anindya De, Elchanan Mossel, and Joe Neeman: Non interactive simulation of correlated distributions is decidable. In Proc. 29th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’18), pp. 2728–2746. ACM Press, 2018. [doi:10.1137/1.9781611975031.174, arXiv:1701.01485]

[9]   Anindya De and Rocco A. Servedio: Efficient deterministic approximate counting for low-degree polynomial threshold functions. In Proc. 46th STOC, pp. 832–841. ACM Press, 2014. [doi:10.1145/2591796.2591800, arXiv:1311.7178]

[10]   Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O’Donnell: On the Fourier tails of bounded functions over the discrete cube. Israel J. Math., 160(1):389–412, 2007. Preliminary version in STOC’06. [doi:10.1007/s11856-007-0068-9]

[11]   Herbert Federer: Geometric Measure Theory. Springer, 1969. [doi:10.1007/978-3-642-62010-2]

[12]   Badih Ghazi, Pritish Kamath, and Madhu Sudan: Decidability of non-interactive simulation of joint distributions. In Proc. 57th FOCS, pp. 545–554. IEEE Comp. Soc. Press, 2016. [doi:10.1109/FOCS.2016.65]

[13]   Steven Heilman: Euclidean partitions optimizing noise stability. Electron. J. Probab., 19(71):1–37, 2014. [doi:10.1214/EJP.v19-3083, arXiv:1211.7138]

[14]   Steven Heilman, Elchanan Mossel, and Joe Neeman: Standard simplices and pluralities are not the most noise stable. Israel J. Math., 213(1):33–53, 2016. Preliminary version in ITCS’15. [doi:10.1007/s11856-016-1320-y, arXiv:1403.0885]

[15]   Michael Hutchings, Frank Morgan, Manuel Ritoré, and Antonio Ros: Proof of the double bubble conjecture. Electron. Res. Announc. Amer. Math. Soc., 6:45–49, 2000. [doi:10.1090/S1079-6762-00-00079-2, arXiv:math/0406017]

[16]   Michael Hutchings, Frank Morgan, Manuel Ritoré, and Antonio Ros: Proof of the double bubble conjecture. Ann. of Math., 155(2):459–489, 2002. [doi:10.2307/3062123, arXiv:math/0406017]

[17]   Marcus Isaksson and Elchanan Mossel: Maximally stable Gaussian partitions with discrete applications. Israel J. Math., 189(1):347–396, 2012. [doi:10.1007/s11856-011-0181-7, arXiv:0903.3362]

[18]   Svante Janson: Gaussian Hilbert Spaces. Cambridge University Press, 1997. [doi:10.1017/CBO9780511526169]

[19]   Gil Kalai: A Fourier-theoretic perspective on the Condorcet paradox and Arrow’s theorem. Adv. in Appl. Math., 29(3):412–426, 2002. [doi:10.1016/S0196-8858(02)00023-4]

[20]   Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell: Optimal inapproximability results for Max-Cut and other 2-variable CSPs? In Proc. 45th FOCS, pp. 146–154. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.49]

[21]   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 [20]. [doi:10.1137/S0097539705447372]

[22]   Pravesh Kothari, Amir Nayyeri, Ryan O’Donnell, and Chenggang Wu: Testing surface area. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), pp. 1204–1214. ACM Press, 2014. [doi:10.1137/1.9781611973402.89]

[23]   Michel Ledoux: Semigroup proofs of the isoperimetric inequality in Euclidean and Gauss space. Bull. des Sciences Mathématiques, 118(6):485–510, 1994.

[24]   Franceso Maggi: Sets of Finite Perimeter and Geometric Variational Problems: An Introduction to Geometric Measure Theory. Cambridge University Press, 2012. [doi:10.1017/CBO9781139108133]

[25]   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, arXiv:math/0503503]

[26]   Joe Neeman: Testing surface area with arbitrary accuracy. In Proc. 46th STOC, pp. 393–397. ACM Press, 2014. [doi:10.1145/2591796.2591807, arXiv:1309.1387]

[27]   John W. Neuberger: Norm of symmetric product compared with norm of tensor product. Linear and Multilinear Algebra, 2(2):115–121, 1974. [doi:10.1080/03081087408817047]

[28]   Ivan Nourdin: Lectures on Gaussian approximations with Malliavin calculus. In Séminaire de Probabilités XLV, pp. 3–89. Springer, 2013. [doi:10.1007/978-3-319-00321-4_1, arXiv:1203.4147]

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

[30]   Prasad Raghavendra and David Steurer: How to round any CSP. In Proc. 50th FOCS, pp. 586–594. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.74]

[31]   Ben W. Reichardt: Proof of the double bubble conjecture in Rn. J. Geom. Anal., 18(1):172–191, 2008. [doi:10.1007/s12220-007-9002-y, arXiv:0705.1601]

[32]   Ben W. Reichardt, Cory Heilmann, Yuan Y. Lai, and Anita Spielman: Proof of the double bubble conjecture in R4 and certain higher dimensional cases. Pacific J. Math., 208(2):347–366, 2003. [PJM].