Theoretical Computer Science
cc.complexity-theory boolean-functions pcp unique-games-conjecture
Updated Tue, 07 Jun 2022 05:12:54 GMT

Proof of Majority is stablest in "reverse" in the MAXCUT hardness paper by Khot et al

This is about Proposition 7.4 here. I think there is a slight error in the proof of this proposition. Basically, authors have taken $g$ to be the odd part of the function $f$. Due to which we can say that $\mathbb{E}[g] = 0$, $\operatorname{Inf}_{i}(g) \leq \operatorname{Inf}_{i}(f)$ for all $i$, and $S_{\rho}(f) \geq S_{\rho}(g) = -S_{-\rho}(g)$.

So, applying MIS on $g$, we get

$S_{\rho}(g) \leq 1 - \frac{2}{\pi}\arccos(\rho) + \epsilon$ for $\rho$ from 0 to 1.

which implies

$-S_{-\rho}(g) \geq -\left(1 - \frac{2}{\pi}\arccos(-\rho) + \epsilon\right)$ for $\rho$ from -1 to 0.


$$S_{\rho}(f) \geq -1 - \frac{2}{\pi}\arccos(\rho) - \epsilon$$

But in the statement of the proposition, authors have written $S_{\rho}(f) \geq 1 - \frac{2}{\pi}\arccos(\rho) - \epsilon$. Is it really an error? Or I am missing something?


"So, applying MIS on $g$"

To apply the Majority is Stablest theorem, you need to apply it to a non-negative parameter $\rho'\in[0,1)$ (read the statement of the theorem). Since in Proposition 7.3 the parameter $\rho\in(-1,0]$ is non-positive, this means you here apply it to $\rho' \stackrel{\rm def}{=} -\rho\in[0,1)$, giving $$\mathbb{S}_{-\rho}(g) \leq 1-\frac{2}{\pi}\arccos(-\rho)+\epsilon = -1+\frac{2}{\pi}\arccos(\rho)+\epsilon$$ using that $\arccos x+\arccos(-x) = \pi$ for all $x$ (This may very well be the part you are missing. $\arccos$ is not an odd function). Then $$\mathbb{S}_{\rho}(f) \geq -\mathbb{S}_{-\rho}(g) \geq -\left(-1+\frac{2}{\pi}\arccos(\rho)+\epsilon\right) = 1-\frac{2}{\pi}\arccos(\rho)-\epsilon$$ as stated.

Comments (1)

  • +0 – Thanks. You are right, I was considering arccos odd function. Stupid mistake. — Dec 15, 2017 at 11:34  

External Links

External links referenced by this document: