Majority is Stablest: Discrete and SoS

by Anindya De, Elchanan Mossel, and Joe Neeman

Theory of Computing, Volume 12(4), pp. 1-50, 2016

Bibliography with links to cited articles

[1]   Per Austrin: Balanced MAX-2-SAT might not be the hardest. In Proc. 39th STOC, pp. 189–197. ACM Press, 2007. Available at ECCC. [doi:10.1145/1250790.1250818]

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

[3]   Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth 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]

[4]   Boaz Barak, Prasad Raghavendra, and David Steurer: Rounding semidefinite programming hierarchies via global correlation. In Proc. 52nd FOCS, pp. 472–481. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.95]

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

[6]   Sergey G. Bobkov: An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space. Ann. Probab., 25(1):206–214, 1997. Available at Project Euclid.

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

[8]   Christer Borell: Geometric bounds on the Ornstein-Uhlenbeck velocity process. Probab. Theory and Related fields, 70(1):1–13, 1985. [doi:10.1007/BF00532234]

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

[10]   Eden Chlamtac and Gyanit Singh: Improved approximation guarantees through higher levels of SDP hierarchies. In Proc. 11th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’08), volume 5171 of LNCS, pp. 49–62. Springer, 2008. [doi:10.1007/978-3-540-85363-3_5]

[11]   Anindya De, Elchanan Mossel, and Joe Neeman: Majority is stablest: discrete and SoS. In Proc. 45th STOC, pp. 477–486. ACM Press, 2013. [doi:10.1145/2488608.2488668, arXiv:1211.1001]

[12]   Nikhil R. Devanur, Subhash Khot, Rishi Saket, and Nisheeth K. Vishnoi: Integrality gaps for sparsest cut and minimum linear arrangement problems. In Proc. 38th STOC, pp. 537–546. ACM Press, 2006. [doi:10.1145/1132516.1132594]

[13]   Irit Dinur, Elchanan Mossel, and Oded Regev: Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843–873, 2009. Preliminary version in STOC’06. [doi:10.1137/07068062X]

[14]   Irit Dinur and Samuel Safra: On the hardness of approximating minimum vertex-cover. Ann. of Math., 162(1):439–485, 2005. Preliminary version in STOC’02. [doi:10.4007/annals.2005.162.439]

[15]   William Feller: An Introduction to Probability Theory and its Applications. John Wiley & Sons, 1968.

[16]   Dan S. Felsenthal and Moshé Machover: The Measurement of Voting Power. Edward Elgar Publishing, 1998.

[17]   Ehud Friedgut and Gil Kalai: Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc., 124(10):2993–3002, 1996. [doi:10.1090/S0002-9939-96-03732-X]

[18]   Ehud Friedgut, Gil Kalai, and Noam Nisan: Elections can be manipulated often. In Proc. 49th FOCS, pp. 243–249. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.87]

[19]    Michel X. Goemans and David P. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, 1995. Preliminary version in STOC’94. [doi:10.1145/227683.227684]

[20]   Dima Grigoriev: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theoret. Comput. Sci., 259(1-2):613–622, 2001. [doi:10.1016/S0304-3975(00)00157-2]

[21]   Dima Grigoriev and Nicolai Vorobjov: Complexity of Null- and Positivstellensatz proofs. Ann. Pure Appl. Logic, 113(1-3):153–160, 2001. [doi:10.1016/S0168-0072(01)00055-0]

[22]   Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]

[23]   David Hilbert: Über die Darstellung definiter Formen als Summe von Formenquadraten. Mathematische Annalen, 32(3):342–350, 1888. [doi:10.1007/BF01443605]

[24]   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]

[25]   Vaithilingam Jeyakumar, Jean Bernard Lasserre, and Guoyin Li: On polynomial optimization over non-compact semi-algebraic sets. J. Optim. Theory and Appl., 163(3):707–718, 2014. [doi:10.1007/s10957-014-0545-3]

[26]   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]

[27]   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]

[28]   Gil Kalai: Social indeterminacy. Econometrica, 72(5):1565–1581, 2004. [doi:10.1111/j.1468-0262.2004.00543.x]

[29]   Subhash Khot: On the power of Unique 2-Prover 1-Round Games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017]

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

[31]   Subhash Khot, Preyas Popat, and Rishi Saket: Approximate Lasserre integrality gap for Unique Games. In Proc. 13th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’10), volume 6302 of LNCS, pp. 298–311. Springer, 2010. [doi:10.1007/978-3-642-15369-3_23]

[32]   Subhash Khot and Rishi Saket: SDP integrality gaps with local 1-embeddability. In Proc. 50th FOCS, pp. 565–574. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.37]

[33]   Subhash Khot and Nisheeth K. Vishnoi: The Unique Games Conjecture, integrality gap for cut problems and embeddability of negative type metrics into 1. J. ACM, 62(1), 2015. Preliminary version in FOCS’05. [doi:10.1145/2629614, arXiv:1305.4581]

[34]   Guy Kindler and Ryan O’Donnell: Gaussian noise sensitivity and Fourier tails. In Proc. 27th IEEE Conf. on Computational Complexity (CCC’12), pp. 137–147. IEEE Comp. Soc. Press, 2012. [doi:10.1109/CCC.2012.35]

[35]   Jean-Louis Krivine: Anneaux préordonnés. J. Analyse Math., 12:307–326, 1964. Available at HAL.

[36]   Jean Bernard Lasserre: Global optimization with polynomials and the problem of moments. SIAM J. Optim., 11(3):796–817, 2001. [doi:10.1137/S1052623400366802]

[37]   Jean Bernard Lasserre: Moments, Positive Polynomials and Their Applications. Imperial College Press, London, 2010. [doi:10.1142/9781848164468_fmatter]

[38]   Henri Lombardi, Nikolai Mnev, and Marie-Françoise Roy: The Positivstellensatz and small deduction rules for systems of inequalities. Mathematische Nachrichten, 181(1):245–259, 1996. [doi:10.1002/mana.3211810110]

[39]   George G. Lorentz: Bernstein polynomials. Chelsea Publishing Company, Inc., 1986.

[40]   László Lovász and Alexander Schrijver: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim., 1(2):166–190, 1991. [doi:10.1137/0801013]

[41]   Elchanan Mossel: Lecture notes on Fourier analysis. Available at author’s website, 2005.

[42]   Elchanan Mossel: Gaussian bounds for noise correlation of functions. Geom. Funct. Anal., 19(6):1713–1756, 2010. Preliminary version in FOCS’08. [doi:10.1007/s00039-010-0047-x, arXiv:math/0703683]

[43]   Elchanan Mossel: A quantitative Arrow theorem. Probab. Theory and Related Fields, 154(1–2):49–88, 2012. [doi:10.1007/s00440-011-0362-7, arXiv:0903.2574]

[44]   Elchanan Mossel and Joe Neeman: Robust optimality of Gaussian noise stability. J. Eur. Math. Soc., 17(2):433–482, 2015. [doi:10.4171/JEMS/507, arXiv:1210.4126]

[45]   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]

[46]   Yurii Nesterov: Global quadratic optimization via conic relaxation. Handbook of Semidefinite Programming. Kluwer, 2000. Available from Citeseer.

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

[48]   Ryan O’Donnell and Yi Wu: An optimal SDP algorithm for Max-Cut, and equally optimal long code tests. In Proc. 40th STOC, pp. 335–344. ACM Press, 2008. [doi:10.1145/1374376.1374425]

[49]    Ryan O’Donnell and Yuan Zhou: Approximability and proof complexity. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1537–1556. ACM Press, 2013. [doi:10.1137/1.9781611973105.111]

[50]   Pablo A. Parrilo: Structured Semidefinite Programs and Semialgebraic Methods in Robustness and Optimization. Ph. D. thesis, California Institute of Technology, 2000. Available from the Caltech Thesis Library.

[51]   Prasad Raghavendra and David Steurer: Integrality gaps for strong SDP relaxations of unique games. In Proc. 50th FOCS, pp. 575–585. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.73]

[52]   Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. SIAM J. Comput., 39(1):323–360, 2009. Preliminary version in STOC’06. [doi:10.1137/070681612, arXiv:math/0510264]

[53]   Grant Schoenebeck: Linear level Lasserre lower bounds for certain k-CSPs. In Proc. 49th FOCS, pp. 593–602. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.74]

[54]   William Fleetwood Sheppard: On the application of the theory of error to cases of normal distribution and normal correlation. Phil. Trans. Royal Soc. London, 192:101–167, 1899. [doi:10.1098/rsta.1899.0003]

[55]   Naum Z. Shor: Class of global minimum bounds of polynomial functions. Cybernetics, 23(6):731–734, 1987. [doi:10.1007/BF01070233]

[56]   Gilbert Stengle: A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Mathematische Annalen, 207(2):87–97, 1974. Available at EuDML. [doi:10.1007/BF01362149]

[57]   Michel Talagrand: On Russo’s approximate 0-1 law. Ann. Probab., 22(3):1576–1587, 1994. Available from Project Euclid.