<p>Following Emil's suggestion and using trial and error, define $P'(x_1, x_2, x_3, x_4) \equiv P(-x_1, x_2, x_3, x_4)$</p>

<p>Instances of $\text{CSP}(P')$ are isomorphic to instances of $\text{CSP}(P)$, via adding a negation in every constraint where $x_1$ appears. Then we apply the theorem on $P'$ after checking that the $\{3,4\}$ fourier coefficient is still positive. We can conclude $P'$ is resistant and therefore $P$ is as well.</p>

CC BY-SA 3.0
2014-10-30T19:21:54.783Z
Something is unsettling about resolving the question this way. Am I supposed to flip $x_1$ in my mind, when $P$ is referred to later in the paper? Like in example 8.7, should I be thinking $P'$ whenever $P$ is mentioned?
Mark
CC BY-SA 3.0
2014-10-30T20:01:17.537Z
As long as it works, yes. No need to be unsettled about it; in an ideal world, the authors might have formulated the theorem and the examples consistently, or explain exactly how to apply one to the other, but life is not perfect.
Emil Jeřábek
CC BY-SA 3.0
2014-10-30T19:14:40.677Z
2014-10-30T19:14:40.677Z
Mark
<p>The paper in question is "<a href="http://arxiv.org/abs/1204.5662" rel="nofollow">On the Usefulness of Predicates</a>", Per Austrin, Johan Håstad (arXiv:1204.5662 [cs.CC]).  </p>

<p>On page 13, Example 8.2 they define a predicate $P$ which is $GLST$ with an additional accepting predicate of all $1$'s. The claim is that this predicate can be shown approximation resistant with Theorem 8.3, which requires that $P$ accept all strings $x_1 x_2 x_3 x_4$ such that $\prod_1 ^3 x_i = -1$ and $x_3 = -x_4$.  </p>

<p>In particular, $P$ should accept $(1,1,-1,1)$ but the definition of $GLST$ provided requires that $x_2 \ne x_4$. </p>

CC BY-SA 3.0
2014-10-30T18:05:31.650Z
Given that their statement of Theorem 8.3 is different from Hast’s anyway, did you try to flip and/or permute some of the bits?
Emil Jeřábek
CC BY-SA 3.0
2014-10-30T19:24:21.793Z
@EmilJeřábek I think by flipping $x_1$ we can resolve the issue, but if you look at Example 8.7, the authors explicitly say that $P$ accepts the troublesome inputs without mentioning any bit flipping.
Mark
<approximation-hardness><csp>
Confusion in 2012 paper by Austrin and Håstad regarding hardness of approximating GLST
Mark
# Confusion in 2012 paper by Austrin and Håstad regarding hardness of approximating GLST

(Asked by: username_0 on 2014-10-30)

The paper in question is "[On the Usefulness of Predicates](http://arxiv.org/abs/1204.5662)", Per Austrin, Johan Håstad (arXiv:1204.5662 [cs.CC]).

On page 13, Example 8.2 they define a predicate $P$ which is $GLST$ with an additional accepting predicate of all $1$'s. The claim is that this predicate can be shown approximation resistant with Theorem 8.3, which requires that $P$ accept all strings $x\_1 x\_2 x\_3 x\_4$ such that $\prod\_1 ^3 x\_i = -1$ and $x\_3 = -x\_4$.

In particular, $P$ should accept $(1,1,-1,1)$ but the definition of $GLST$ provided requires that $x\_2 \ne x\_4$.

**Tags:** approximation-hardness, csp

> **Comments:**
> **username_1**: Given that their statement of Theorem 8.3 is different from Hast’s anyway, did you try to flip and/or permute some of the bits?  
> **username_0**: @EmilJeřábek I think by flipping $x_1$ we can resolve the issue, but if you look at Example 8.7, the authors explicitly say that $P$ accepts the troublesome inputs without mentioning any bit flipping.  

---

## 1 answers

### Answer by username_0 on 2014-10-30. Score: 1 | Accepted answer

Following Emil's suggestion and using trial and error, define $P'(x\_1, x\_2, x\_3, x\_4) \equiv P(-x\_1, x\_2, x\_3, x\_4)$

Instances of $\text{CSP}(P')$ are isomorphic to instances of $\text{CSP}(P)$, via adding a negation in every constraint where $x\_1$ appears. Then we apply the theorem on $P'$ after checking that the $\{3,4\}$ fourier coefficient is still positive. We can conclude $P'$ is resistant and therefore $P$ is as well.

> **Comments:**
> **username_0**: Something is unsettling about resolving the question this way. Am I supposed to flip $x_1$ in my mind, when $P$ is referred to later in the paper? Like in example 8.7, should I be thinking $P'$ whenever $P$ is mentioned?  
> **username_1**: As long as it works, yes. No need to be unsettled about it; in an ideal world, the authors might have formulated the theorem and the examples consistently, or explain exactly how to apply one to the other, but life is not perfect.  

---

