Theory of Computing
-------------------
Title     : Majority is Stablest: Discrete and SoS
Authors   : Anindya De, Elchanan Mossel, and Joe Neeman
Volume    : 12
Number    : 4
Pages     : 1-50
URL       : https://theoryofcomputing.org/articles/v012a004

Abstract
--------

The "Majority is Stablest" Theorem has numerous applications in
hardness of approximation and social choice theory. We give a new
proof of the "Majority is Stablest" Theorem by induction on the
dimension of the discrete cube. Unlike the previous proof, it uses
neither the "invariance principle" nor Borell's result in Gaussian
space. Moreover, the new proof allows us to derive a proof of
"Majority is Stablest" in a constant level of the Sum of Squares
hierarchy. This implies in particular that the Khot-Vishnoi instance
of Max-Cut does not provide a gap instance for the Lasserre hierarchy.

An extended abstract of this paper appeared in the Proceedings of
the 45th ACM Symposium on the Theory of Computing, 2013.