Sangxia Huang: Majority is Stablest: Discrete and SoS

Lunch is served at 12:00 noon (register at doodle.com/e6kuh3z8qqte8ysf by Thu Dec 13 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene at 1:10 pm for ca two hours of more technical discussions

Abstract

Consider a vote by n people on a Yes/No question and a voting scheme that decides the outcome of the vote based on the n inputs. The Majority is Stablest Theorem says that among all voting schemes where the number of possible ways to vote so that the result in Yes and so that the result in No are the same, and that no voter has large influence on the result, Majority is the stablest scheme (result least likely to be affected by flipping a small number of inputs).

The Majority is Stablest Theorem has numerous applications in hardness of approximation and social choice theory. The proof by [Mossel, O'Donnell, Oleszkiewicz 10] uses deep results in Gaussian analysis and an Invariance Principle that allows to deduce the discrete result from the Gaussian one.

Recently, Anindya De, Elchanan Mossel and Joe Neeman provided a short general proof of the Majority is Stablest Theorem that does not rely on Gaussian analysis and the Invariance Principle. The new proof can also be transformed into a "Sum of Squares" proof, thus showing that the Khot-Vishnoi instance of Max-Cut does not provide an integrality gap instance for Max-Cut in the Lasserre hierarchy.

In this seminar, we introduce basic notions of Boolean function analysis. We present the ideas of both the "Invariance Principle"-based proof and the new proof. In the reading group that follows the seminar, we discuss details of the new proof as well as (time permits) the Sum of Squares proof of the Majority is Stablest Theorem.