<blockquote>
  <p><em>"So, applying MIS on $g$"</em></p>
</blockquote>

<p>To apply the Majority is Stablest theorem, you need to apply it to a <em>non-negative</em> 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$ <em>(This may very well be the part you are missing. $\arccos$ is not an odd function)</em>.
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.</p>

CC BY-SA 3.0
2017-12-15T11:34:02.610Z
Thanks. You are right, I was considering arccos odd function. Stupid mistake.
Vimal Raj Sharma
CC BY-SA 3.0
2017-12-15T09:28:40.320Z
2017-12-15T09:28:40.320Z
Clement C.
<p>This is about Proposition 7.4 <a href="http://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf" rel="nofollow noreferrer" title="here">here</a>. 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)$.</p>

<p>So, applying MIS on $g$, we get </p>

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

<p>which implies</p>

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

<p>Therefore,</p>

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

<p>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?</p>

<cc.complexity-theory><boolean-functions><pcp><unique-games-conjecture>
Proof of Majority is stablest in "reverse" in the MAXCUT hardness paper by Khot et al
Vimal Raj Sharma
# Proof of Majority is stablest in "reverse" in the MAXCUT hardness paper by Khot et al

(Asked by: username_0 on 2017-12-14)

This is about Proposition 7.4 [here](http://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf "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.

Therefore,

$$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?

**Tags:** cc.complexity-theory, boolean-functions, pcp, unique-games-conjecture


---

## 1 answers

### Answer by username_1 on 2017-12-15. Score: 4 | Accepted answer

> *"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:**
> **username_0**: Thanks. You are right, I was considering arccos odd function. Stupid mistake.  

---

