1
$\begingroup$

The paper in question is "On the Usefulness of Predicates", 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$.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$
    – Emil Jeřábek
    Commented Oct 30, 2014 at 18:05
  • $\begingroup$ @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. $\endgroup$
    – Mark
    Commented Oct 30, 2014 at 19:24

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Mark
    Commented Oct 30, 2014 at 19:21
  • 4
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Oct 30, 2014 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.