§11.7: Highlight: Majority Is Stablest Theorem

The Majority Is Stablest Theorem (to be proved at the end of this section) was originally conjectured in 2004 [KKMO04,KKMO07]. The motivation came from studying the approximability of the Max-Cut CSP.

Recall that Max-Cut is perhaps the simplest possible constraint satisfaction problem: the domain of the variables is $\Omega = \{-1,1\}$ and the only constraint allowed is the binary non-equality predicate, $\neq : \{-1,1\}^2 \to \{0,1\}$. As we mentioned briefly in Chapter 7.3, Goemans and Williamson [GW95] gave a very sophisticated efficient algorithm using “semidefinite programming” which $(c_{\text{GW}} \beta, \beta)$-approximates Max-Cut for every $\beta$, where $c_{\text{GW}} \approx .8786$ is a certain trigonometric constant.

Turning to hardness of approximation, we know from Theorem 7.41 (developed in [KKMO04]) that to prove UG-hardness of $(\alpha+\delta, \beta-\delta)$-approximating Max-Cut, it suffices to construct an $(\alpha,\beta)$-Dictator-vs.-No-Notables test which uses the predicate $\neq$. As we’ll see in this section, the quality of the most natural such test can be easily inferred from the Majority Is Stablest Theorem. Assuming that theorem (as Khot et al. [KKMO04] did), we get a surprising conclusion: It’s UG-hard to approximate the Max-Cut CSP any better than the Goemans–Williamson Algorithm does. In other words, the peculiar approximation guarantee of Goemans and Williamson on the very simple Max-Cut problem is optimal (assuming the Unique Games Conjecture). Let’s demystify this somewhat, starting with a description of the Goemans–Williamson Algorithm. Let $G = (V,E)$ be an $n$-vertex input graph for the algorithm; we’ll write $(\boldsymbol{v}, \boldsymbol{w}) \sim E$ to denote that $(\boldsymbol{v}, \boldsymbol{w})$ is a uniformly random edge (i.e., $\neq$-constraint) in the graph. The first step of the Goemans–Williamson Algorithm is to solve following optimization problem: \begin{equation} \label{eqn:gw-sdp} \tag{SDP} \begin{aligned} \text{maximize}& \quad \mathop{\bf E}_{(\boldsymbol{v},\boldsymbol{w}) \sim E}\left[\tfrac{1}{2} - \tfrac{1}{2} \langle \vec{U}(\boldsymbol{v}), \vec{U}(\boldsymbol{w}) \rangle\right] \\ \text{subject to}& \quad \vec{U} : V \to S^{n-1}. \end{aligned} \end{equation} Here $S^{n-1}$ denotes the set of all unit vectors in ${\mathbb R}^n$. Somewhat surprisingly, since this optimization problem is a “semidefinite program” it can be solved in polynomial time using the Ellipsoid Algorithm. (Technically, it can only be solved up to any desired additive tolerance $\epsilon > 0$, but we’ll ignore this point.) Let’s write $\mathrm{SDPOpt}(G)$ for the optimum value of \eqref{eqn:gw-sdp}, and $\mathrm{Opt}(G)$ for the optimum Max-Cut value for $G$. We claim that \eqref{eqn:gw-sdp} is a relaxation of the Max-Cut CSP on input $G$, and therefore \[ \mathrm{SDPOpt}(G) \geq \mathrm{Opt}(G). \] To see this, simply note that if $F^* : V \to \{-1,1\}$ is an optimal assignment (“cut”) for $G$ then we can define $\vec{U}(v) = (F^*(v), 0, \dots, 0) \in S^{n-1}$ for each $v \in V$ and achieve the optimal cut value $\mathrm{Val}_G(F^*)$ in \eqref{eqn:gw-sdp}.

The second step of the Goemans–Williamson Algorithm might look familiar from Fact 7 and Remark 8. Let $\vec{U}^* : V \to S^{n-1}$ be the optimal solution for \eqref{eqn:gw-sdp}, achieving $\mathrm{SDPOpt}(G)$; abusing notation we’ll write $\vec{U}^*(v) = \vec{v}$. The algorithm now chooses $\vec{\boldsymbol{g}} \sim \mathrm{N}(0,1)^n$ at random and outputs the assignment (cut) $\boldsymbol{F} : V \to \{-1,1\}$ defined by $\boldsymbol{F}(v) = \mathrm{sgn}(\langle \vec{v}, \vec{\boldsymbol{g}} \rangle)$. Let’s analyze the (expected) quality of this assignment. The probability the algorithm’s assignment $\boldsymbol{F}$ cuts a particular edge $(v,w) \in E$ is \[ \mathop{\bf Pr}_{\vec{\boldsymbol{g}} \sim \mathrm{N}(0,1)^n}[\mathrm{sgn}(\langle \vec{v}, \vec{\boldsymbol{g}} \rangle) \neq \mathrm{sgn}(\langle \vec{w}, \vec{\boldsymbol{g}} \rangle)]. \] This is precisely the probability that $\mathrm{sgn}(\boldsymbol{z}) \neq \mathrm{sgn}(\boldsymbol{z}’)$ when $(\boldsymbol{z}, \boldsymbol{z}’)$ is a pair of $\langle \vec{v}, \vec{w}\rangle$-correlated $1$-dimensional Gaussians. Writing $\angle(\vec{v},\vec{w}) \in [0,\pi]$ for the angle between the unit vectors $\vec{v}, \vec{w}$, we conclude from Sheppard’s Formula (see equation 11.1.(2)) that \[ \mathop{\bf Pr}_{\vec{\boldsymbol{g}}}[\boldsymbol{F} \text{ cuts edge $(v,w)$}] = \frac{\angle(\vec{v}, \vec{w})}{\pi}. \] By linearity of expectation we can compute the expected value of the algorithm’s assignment $\boldsymbol{F}$: \begin{equation} \mathop{\bf E}_{\vec{\boldsymbol{g}}}[\mathrm{Val}_G(\boldsymbol{F})] = \mathop{\bf E}_{(\boldsymbol{v},\boldsymbol{w}) \sim E}\left[\angle(\vec{\boldsymbol{v}}, \vec{\boldsymbol{w}})/\pi\right]. \label{eqn:gw-gets}
On the other hand, by definition we have \begin{equation} \mathrm{SDPOpt}(G) = \mathop{\bf E}_{(\boldsymbol{v},\boldsymbol{w}) \sim E}\left[\tfrac{1}{2}-\tfrac{1}{2}\cos \angle(\vec{\boldsymbol{v}}, \vec{\boldsymbol{w}})\right]. \label{eqn:gw-sdpopt} \end{equation} It remains to compare \eqref{eqn:gw-gets} and \eqref{eqn:gw-sdpopt}. Define \begin{equation} \label{eqn:cgw-def} c_{\text{GW}} = \min_{\theta \in [0,\pi]} \left\{\frac{\theta/\pi}{\tfrac{1}{2}-\tfrac{1}{2} \cos \theta}\right\} \approx .8786. \end{equation} Then from \eqref{eqn:gw-gets} and \eqref{eqn:gw-sdpopt} we immediately get \[ \mathop{\bf E}_{\vec{\boldsymbol{g}}}[\mathrm{Val}_G(\boldsymbol{F})] \geq c_{\text{GW}} \cdot \mathrm{SDPOpt}(G) \geq c_{\text{GW}} \cdot \mathrm{Opt}(G); \] i.e., in expectation the Goemans–Williamson Algorithm delivers a cut of value at least $c_{\text{GW}}$ times the Max-Cut. In other words, it’s a $(c_{\text{GW}} \beta, \beta)$-approximation algorithm, as claimed. By being a little bit more careful about this analysis (exercise) you can show following additional result:

Theorem 71 [GW95]. Let $\theta \in [\theta^*, \pi]$, where $\theta^* \approx .74\pi$ is the minimizing $\theta$ in \eqref{eqn:cgw-def} (also definable as the positive solution of $\tan(\theta/2) = \theta$). Then on any graph $G$ with $\mathrm{SDPOpt}(G) \geq \tfrac{1}{2} – \tfrac{1}{2} \cos \theta$, the Goemans–Williamson Algorithm produces a cut of (expected) value at least $\theta/\pi$. In particular, the algorithm is a $(\theta/\pi, \tfrac{1}{2} – \tfrac{1}{2} \cos \theta)$-approximation algorithm for Max-Cut.

Example 72 Consider the Max-Cut problem on the $5$-vertex cycle graph ${\mathbb Z}_5$. The best bipartition of this graph cuts $4$ out of the $5$ edges; hence $\mathrm{Opt}({\mathbb Z}_5) = \frac45$. In the exercises you are asked to show that taking \[ \vec{U}(v) = (\cos \tfrac{4\pi v}{5}, \sin \tfrac{4\pi v}{5}), \quad v \in {\mathbb Z}_5, \] in the semidefinite program \eqref{eqn:gw-sdp} establishes that $\mathrm{SDPOpt}({\mathbb Z}_5) \geq \tfrac{1}{2} – \tfrac{1}{2} \cos \frac{4\pi}{5}$. (These are actually unit vectors in ${\mathbb R}^2$ rather than in ${\mathbb R}^5$ as \eqref{eqn:gw-sdp} requires, but we can pad out the last three coordinates with zeroes.) This example shows that the Goemans–Williamson analysis in Theorem 71 lower-bounding $\mathrm{Opt}(G)$ in terms of $\mathrm{SDPOpt}(G)$ cannot be improved (at least when $\mathrm{SDPOpt}(G) = \frac45$). This is termed an optimal integrality gap. In fact, Theorem 71 also implies that $\mathrm{SDPOpt}({\mathbb Z}_5)$ must equal $\tfrac{1}{2} – \tfrac{1}{2} \cos \frac{4\pi}{5}$, for if it were greater, the theorem would falsely imply that $\mathrm{Opt}({\mathbb Z}_5) > \frac45$. Note that the Goemans–Williamson Algorithm actually finds the maximum cut when run on the cycle graph ${\mathbb Z}_5$. For a related example, see the exercises.

Now we explain the result of Khot et al. [KKMO04], that the Majority Is Stablest Theorem implies it’s UG-hard to approximate Max-Cut better than the Goemans–Williamson Algorithm does:

Theorem 73 [KKMO04]. Let $\theta \in (\frac{\pi}{2}, \pi)$. Then for any $\delta > 0$ it’s UG-hard to $(\theta/\pi + \delta, \tfrac{1}{2} – \tfrac{1}{2} \cos\theta)$-approximate Max-Cut.

Proof: It follows from Theorem 7.41 that we just need to construct a $(\theta/\pi, \tfrac{1}{2} – \tfrac{1}{2} \cos\theta)$-Dictator-vs.-No-Notables test using the predicate $\neq$. (See the exercises for an extremely minor technical point.) It’s very natural to try the following, with $\beta = \tfrac{1}{2} – \tfrac{1}{2} \cos \theta \in (\frac12, 1)$:

$\boldsymbol{\beta}$-Noise Sensitivity Test Given query access to $f : \{-1,1\}^n \to \{-1,1\}$:

  • Choose ${\boldsymbol{x}} \sim \{-1,1\}^n$ and form ${\boldsymbol{x}}’$ by reversing each bit of ${\boldsymbol{x}}$ independently with probability $\beta = \tfrac{1}{2} – \tfrac{1}{2} \cos\theta$. In other words let $({\boldsymbol{x}}, {\boldsymbol{x}}’)$ be a pair of $\cos\theta$-correlated strings. (Note that $\cos\theta < 0$.)
  • Query $f$ at ${\boldsymbol{x}}$, ${\boldsymbol{x}}’$.
  • Accept if $f({\boldsymbol{x}}) \neq f({\boldsymbol{x}}’)$.

By design, \begin{equation} \label{eqn:kkmo-acceptance} \mathop{\bf Pr}[\text{the test accepts } f] = \mathbf{NS}_\beta[f] = \tfrac{1}{2} – \tfrac{1}{2} \mathbf{Stab}_{\cos \theta}[f]. \end{equation} (We might also express this as “$\mathbf{RS}_f(\theta)$”.) In particular, if $f$ is a dictator, it’s accepted with probability exactly $\beta = \tfrac{1}{2} – \tfrac{1}{2} \cos \theta$. To complete the proof that this is a $(\theta/\pi, \tfrac{1}{2} – \tfrac{1}{2} \cos\theta)$-Dictator-vs.-No-Notables test, let’s suppose $f : \{-1,1\}^n \to [-1,1]$ has no $(\epsilon,\epsilon)$-notable coordinates and show that \eqref{eqn:kkmo-acceptance} is at most $\theta/\pi + o_\epsilon(1)$. (Regarding $f$ having range $[-1,1]$, recall Remark 7.39.)

At first it might look like we can immediately apply the Majority Is Stablest Theorem; however, the theorem’s inequality goes the “wrong way” and the correlation parameter $\rho = \cos \theta$ is negative. These two difficulties actually cancel each other out. Note that \begin{align} \mathop{\bf Pr}[\text{the test accepts } f] &= \tfrac{1}{2} – \tfrac{1}{2} \mathbf{Stab}_{\cos \theta}[f] \nonumber\\ &= \tfrac{1}{2} – \tfrac{1}{2} \sum_{k=0}^n (\cos \theta)^{k} \mathbf{W}^{k}[f] \nonumber\\ &\leq \tfrac{1}{2} + \tfrac{1}{2} \sum_{\text{$k$ odd}} (-\cos \theta)^{k} \mathbf{W}^{k}[f] \tag{since $\cos \theta < 0$} \nonumber\\ &= \tfrac{1}{2} + \tfrac{1}{2} \mathbf{Stab}_{-\cos\theta}[f^\mathrm{odd}], \label{eqn:finish-kkmo} \end{align} where $f^\mathrm{odd} : \{-1,1\}^n \to [-1,1]$ is the odd part of $f$ (see Exercise 1.8) defined by \[ f^\mathrm{odd}(x) = \tfrac{1}{2}(f(x) - f(-x)) = \sum_{|S|\text{ odd}} \widehat{f}(S)\,x^S. \] Now we’re really in a position to apply the Majority Is Stablest Theorem to $f^\mathrm{odd}$, because $-\cos\theta \in (0,1)$, $\mathop{\bf E}[f^\mathrm{odd}] = 0$, and $f^\mathrm{odd}$ has no $(\epsilon,\epsilon)$-notable coordinates (since it’s formed from $f$ by just dropping some terms in the Fourier expansion). Using $-\cos\theta = \cos(\pi – \theta)$, the result is that \[ \mathbf{Stab}_{-\cos\theta}[f^\mathrm{odd}] \leq 1 – \tfrac{2}{\pi} \arccos(\cos(\pi – \theta)) + o_\epsilon(1) = 2\theta/\pi – 1 + o_\epsilon(1). \] Putting this into \eqref{eqn:finish-kkmo} yields \[ \mathop{\bf Pr}[\text{the test accepts } f] \leq \tfrac{1}{2} + \tfrac{1}{2} (2\theta/\pi – 1 + o_\epsilon(1)) = \theta/\pi + o_\epsilon(1), \] as needed. $\Box$

Remark 74 There’s actually still a mismatch between the algorithmic guarantee of Theorem 71 and the UG-hardness result Theorem 73, concerning the case of $\theta \in (\frac{\pi}{2}, \theta^*)$. In fact, for these values of $\theta$ — i.e., $\tfrac{1}{2} \leq \beta \lessapprox .8446$ — neither result is sharp; see O’Donnell and Wu [OW08].

Remark 75 If we want to prove UG-hardness of $(\theta’/\pi + \delta, \tfrac{1}{2} – \tfrac{1}{2} \cos\theta’)$-approximating Max-Cut, we don’t need the full version of Borell’s Isoperimetric Theorem; we only need the volume-$\tfrac{1}{2}$ case with parameter $\theta = \pi – \theta’$. Corollary 44 gave a simple proof of this result for $\theta = \frac{\pi}{4}$, hence $\theta’ = \frac{3}{4} \pi$. This yields UG-hardness of $(\tfrac34 + \delta, \tfrac{1}{2} + \frac{1}{2\sqrt{2}})$-approximating Max-Cut. The ratio between $\alpha$ and $\beta$ here is approximately $.8787$, very close to the Goemans–Williamson constant $c_{\text{GW}} \approx .8786$.

Finally, we will prove the General-Volume Majority Is Stablest Theorem, by using the Invariance Principle to reduce it to Borell’s Isoperimetric Theorem.

General-Volume Majority Is Stablest Theorem Let $f : \{-1,1\}^n \to [0,1]$. Suppose that $\mathbf{MaxInf}[f] \leq \epsilon$, or more generally, that $f$ has no $(\epsilon, \frac{1}{\log(1/\epsilon)})$-notable coordinates. Then for any $0 \leq \rho < 1$, \begin{equation} \label{eqn:mist} \mathbf{Stab}_\rho[f] \leq \Lambda_\rho(\mathop{\bf E}[f]) + O\bigl(\tfrac{\log \log (1/\epsilon)}{\log(1/\epsilon)}\bigr) \cdot \tfrac{1}{1-\rho}. \end{equation} (Here the $O(\cdot)$ bound has no dependence on $\rho$.)

Proof: The proof involves using the Basic Invariance Principle twice (in the form of Corollary 68). To facilitate this we introduce $f’ = \mathrm{T}_{1-\delta} f$, where (with foresight) we choose \[ \delta = 3 \tfrac{\log \log(1/\epsilon)}{\log(1/\epsilon)}. \] (We may assume $\epsilon$ is sufficiently small so that $0 < \delta \leq \frac{1}{20}$.) Note that $\mathop{\bf E}[f'] = \mathop{\bf E}[f]$ and that \[ \mathbf{Stab}_\rho[f'] = \sum_{S \subseteq [n]} \rho^{|S|} (1-\delta)^{2|S|} \widehat{f}(S)^2 = \mathbf{Stab}_{\rho(1-\delta)^2}[f]. \] But \begin{equation} \label{eqn:mist-tradeoff} \bigl|\mathbf{Stab}_{\rho(1-\delta)^2}[f] – \mathbf{Stab}_{\rho}[f]\bigr| \leq (\rho – \rho(1-\delta)^2) \cdot \tfrac{1}{1-\rho} \cdot \mathop{\bf Var}[f] \leq 2\delta \cdot \tfrac{1}{1-\rho} \end{equation} by Exercise 2.40, and with our choice of $\delta$ this can be absorbed into the error of \eqref{eqn:mist}. Thus it suffices to prove \eqref{eqn:mist} with $f’$ in place of $f$.

Let $\text{Sq} : {\mathbb R} \to {\mathbb R}$ be the continuous function which agrees with $t \mapsto t^2$ for $t \in [0,1]$ and is constant outside $[0,1]$. Note that $\text{Sq}$ is $2$-Lipschitz. We will apply the second part of Corollary 68 with “$h$” set to $\mathrm{T}_{\sqrt{\rho}} f$ (and thus $\mathrm{T}_{1-\delta} h = \mathrm{T}_{\sqrt{\rho}} f’$). This is valid since the variance and $(1-\delta)$-stable influences of $h$ are only smaller than those of $f$. Thus \begin{equation} \label{eqn:mist-halfway} \left|\mathop{\bf E}_{{\boldsymbol{x}} \sim \{-1,1\}^n}[\text{Sq}(\mathrm{T}_{\sqrt{\rho}}f'({\boldsymbol{x}}))] – \mathop{\bf E}_{\boldsymbol{g} \sim \mathrm{N}(0,1)^n}[\text{Sq}(\mathrm{T}_{\sqrt{\rho}} f'(\boldsymbol{g}))]\right| \leq O(\epsilon^{\delta/3}) = O\bigl(\tfrac{1}{\log(1/\epsilon)}\bigr), \end{equation} using our choice of $\delta$. (In fact, it’s trading off this error with \eqref{eqn:mist-tradeoff} that led to our choice of $\delta$.) Now $\mathrm{T}_{\sqrt{\rho}} f’({\boldsymbol{x}}) = \mathrm{T}_{(1-\delta)\sqrt{\rho}} f({\boldsymbol{x}})$ is always bounded in $[0,1]$, so \[ \text{Sq}(\mathrm{T}_{\sqrt{\rho}} f'({\boldsymbol{x}})) = (\mathrm{T}_{\sqrt{\rho}} f'({\boldsymbol{x}}))^2 \quad \implies \quad \mathop{\bf E}_{{\boldsymbol{x}} \sim \{-1,1\}^n}[\text{Sq}(\mathrm{T}_{\sqrt{\rho}}f'({\boldsymbol{x}}))] = \mathbf{Stab}_\rho[f']. \] Furthermore, $\mathrm{T}_{\sqrt{\rho}} f’(\boldsymbol{g})$ is the same as $\mathrm{U}_{\sqrt{\rho}} f’(\boldsymbol{g})$ because $f’$ is a multilinear polynomial. (Both are equal to $f’(\rho \boldsymbol{g})$; see Fact 13.) Thus in light of \eqref{eqn:mist-halfway}, to complete the proof of \eqref{eqn:mist} it suffices to show \begin{equation} \label{eqn:mist-suffices} \left|\mathop{\bf E}_{\boldsymbol{g} \sim \mathrm{N}(0,1)^n}[\text{Sq}(\mathrm{U}_{\sqrt{\rho}} f'(\boldsymbol{g}))] – \Lambda_\rho(\mathop{\bf E}[f'])\right| \leq O\bigl(\tfrac{1}{\log(1/\epsilon)}\bigr). \end{equation}

Define the function $F : {\mathbb R}^n \to [0,1]$ by \[ F(g) = \mathrm{trunc}_{[0,1]}(f’(g)) = \begin{cases} 0 & \text{if $f’(g) < 0$,} \\ f’(g) & \text{if $f’(g) \in [0,1]$,}\\ 1 & \text{if $f’(g) >1$.} \end{cases} \] We will establish the following two inequalities, which together imply \eqref{eqn:mist-suffices}: \begin{gather} \left|\mathop{\bf E}_{\boldsymbol{g} \sim \mathrm{N}(0,1)^n}[\text{Sq}(\mathrm{U}_{\sqrt{\rho}} f'(\boldsymbol{g}))] – \mathop{\bf E}_{\boldsymbol{g} \sim \mathrm{N}(0,1)^n}[\text{Sq}(\mathrm{U}_{\sqrt{\rho}} F(\boldsymbol{g}))]\right| \leq O\bigl(\tfrac{1}{\log(1/\epsilon)}\bigr), \label{eqn:mist1} \\ \mathop{\bf E}_{\boldsymbol{g} \sim \mathrm{N}(0,1)^n}[\text{Sq}(\mathrm{U}_{\sqrt{\rho}} F(\boldsymbol{g}))] \leq \Lambda_\rho(\mathop{\bf E}[f']) + O\bigl(\tfrac{1}{\log(1/\epsilon)}\bigr). \label{eqn:mist2} \end{gather} Both of these inequalities will in turn follow from \begin{equation} \label{eqn:f’-to-F} \mathop{\bf E}_{\boldsymbol{g} \sim \mathrm{N}(0,1)^n}[|f'(\boldsymbol{g}) - F(\boldsymbol{g})|] = \mathop{\bf E}_{\boldsymbol{g} \sim \mathrm{N}(0,1)^n}[\mathrm{dist}_{[0,1]}(f’(\boldsymbol{g}))] \leq O\bigl(\tfrac{1}{\log(1/\epsilon)}\bigr). \end{equation} Let’s show how \eqref{eqn:mist1} and \eqref{eqn:mist2} follow from \eqref{eqn:f’-to-F}, leaving the proof of \eqref{eqn:f’-to-F} to the end. For \eqref{eqn:mist1}, \begin{align*} \left|\mathop{\bf E}[\text{Sq}(\mathrm{U}_{\sqrt{\rho}} f'(\boldsymbol{g}))] – \mathop{\bf E}[\text{Sq}(\mathrm{U}_{\sqrt{\rho}} F(\boldsymbol{g}))] \right| &\leq 2 \mathop{\bf E}[|\mathrm{U}_{\sqrt{\rho}} f'(\boldsymbol{g}) - \mathrm{U}_{\sqrt{\rho}} F(\boldsymbol{g})|]\\ &\leq 2 \mathop{\bf E}[|f'(\boldsymbol{g}) - F(\boldsymbol{g})|] \leq O\bigl(\tfrac{1}{\log(1/\epsilon)}\bigr), \end{align*} where the first inequality used that $\text{Sq}$ is $2$-Lipschitz, the second inequality used the fact that $\mathrm{U}_{\sqrt{\rho}}$ is a contraction on $L^1({\mathbb R}^n,\gamma)$, and the third inequality was \eqref{eqn:f’-to-F}. As for \eqref{eqn:mist2}, $\mathrm{U}_{\sqrt{\rho}} F$ is bounded in $[0,1]$ since $F$ is. Thus \[ \mathop{\bf E}[\text{Sq}(\mathrm{U}_{\sqrt{\rho}} F(\boldsymbol{g}))] = \mathop{\bf E}[(\mathrm{U}_{\sqrt{\rho}} F(\boldsymbol{g}))^2] = \mathbf{Stab}_\rho[F] \leq \Lambda_\rho(\mathop{\bf E}[F(\boldsymbol{g})]), \] where we used Borell’s Isoperimetric Theorem. But $|\mathop{\bf E}[F(\boldsymbol{g})] – \mathop{\bf E}[f'(\boldsymbol{g})]| \leq O\bigl(\tfrac{1}{\log(1/\epsilon)}\bigr)$ by \eqref{eqn:f’-to-F}, and $\Lambda_\rho$ is easily shown to be $2$-Lipschitz (exercise). This establishes \eqref{eqn:mist2}.

It therefore remains to show \eqref{eqn:f’-to-F}, which we do by applying the Invariance Principle one more time. Taking $\psi$ to be the $1$-Lipschitz function $\mathrm{dist}_{[0,1]}$ in Corollary 68 we deduce \begin{align*} \left|\mathop{\bf E}_{\boldsymbol{g} \sim \mathrm{N}(0,1)^n}[\mathrm{dist}_{[0,1]}(f’(\boldsymbol{g}))] – \mathop{\bf E}_{{\boldsymbol{x}} \sim \{-1,1\}^n}[\mathrm{dist}_{[0,1]}(f’({\boldsymbol{x}}))]\right| \leq O(\epsilon^{\delta/3}) = O\bigl(\tfrac{1}{\log(1/\epsilon)}\bigr). \end{align*} But $\mathop{\bf E}[\mathrm{dist}_{[0,1]}f’({\boldsymbol{x}})] = 0$ since $f’({\boldsymbol{x}}) = \mathrm{T}_{1-\delta} f({\boldsymbol{x}}) \in [0,1]$ always. This establishes \eqref{eqn:f’-to-F} and completes the proof. $\Box$

We conclude with one more application of the Majority Is Stablest Theorem. Recall Kalai’s version of Arrow’s Theorem from Chapter 2.5, i.e., Theorem 2.55. It states that in a $3$-candidate Condorcet election using the voting rule $f : \{-1,1\}^n \to \{-1,1\}$, the probability of having a Condorcet winner — often called a rational outcome — is precisely $\tfrac34 – \tfrac34\mathbf{Stab}_{-1/3}[f]$. As we saw in the proof of Theorem 73 near \eqref{eqn:finish-kkmo}, this is in turn at most $\tfrac34 + \tfrac34\mathbf{Stab}_{1/3}[f^\mathrm{odd}]$, with equality if $f$ is already odd. It follows from the Majority Is Stablest Theorem that among all voting rules with $\epsilon$-small influences (a condition all reasonable voting rules should satisfy), majority rule is the “most rational”. Thus we see that the principle of representative democracy can be derived using analysis of Boolean functions.

2 comments to §11.7: Highlight: Majority Is Stablest Theorem

Leave a Reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>