How does the strong form of the PCP theorem imply the inapproximability of Max-XORSAT?
Theorem 11.4 For any constant $\delta > 0$, every problem in NP has probabilistically checkable proofs of length poly($n$), where the verifier flips $O(\log n)$ coins and looks at three bits of the proof, with completeness $1-\delta$ and soundness $1/2+\delta$.
Moreover, the conditions under which <PERSON> accepts are extremely simple - namely, if the parity of these three bits is even.
This theorem has powerful consequences for inapproximability. If we write down all the triplets of bits that <PERSON> could look at, we get a system of linear equations mod 2. If <PERSON> takes his best shot at a proof, the probability that <PERSON> will accept is the largest fraction of these equations that can be simultaneously satisfied. Thus even if we know that this fraction is either at least $1-\delta$ or at most $1/2+\delta$, it is NP-hard to tell which. This implies that it is NP-hard to approximate Max-XORSAT within any constant factor better than $1/2$.
First, I don't think it can be as simple as just checking that the parity is even. <PERSON> could just make <PERSON> accept anything by handing him a proof of all zeros, and make him reject anything with a proof of all ones. Surely the parity must instead equal some value that <PERSON> computes along the way.
Further, It's not a priori clear to me that <PERSON> would select every triplet with equal likelihood. If that wasn't the case, wouldn't it be possible for a no-instance to yield a Max-XORSAT formula where more than $1/2+\delta$ of the clauses can be satisfied even though <PERSON> accepts with probability less than $1/2+\delta$?
Let's take a degenerate case as an example. <PERSON> asks <PERSON> to help him decide whether a given sequence of $n$ bits $\mathbf{b}$ is all ones - $\mathbf{b=1}$ for short. This problem is trivially in NP. And <PERSON> clearly doesn't need <PERSON>'s help. 768
But he can go out of his way to use it anyway. Here's what they do:
First <PERSON> gives <PERSON> a PCP $\mathbf{x} \in {0,1}^n$ (let's assume $n \gg 3$). Then <PERSON> checks if $\mathbf{b=1}.$ If it is, he checks that $x_1 \oplus x_2 \oplus x_3 = 1$ holds in <PERSON>'s PCP. Otherwise, he checks either $x_1 \oplus x_2 \oplus x_3 = 1$ or $\overline{x_1} \oplus \overline{x_2} \oplus \overline{x_3} = 1$ (note that these can't both be satisfied) with equal probability 0.45. Or with probability 0.1 he checks $x_i \oplus x_j \oplus x_k = 1$ for a uniformly random triplet.
<PERSON> can thus convince <PERSON> that $\mathbf{b=1}$ by giving him, for example, the proof consisting of all ones. But if $\mathbf{b\neq1}$ there's no proof that <PERSON> accepts with probability greater than 0.55. This gives PCP's with completeness $1-\delta$ (indeed we also have completeness 1) and soundness $1/2+\delta$ where $\delta = 0.05$.
Now what's the Max-XORSAT formula corresponding to $\mathbf{b\neq1}$? Well, <PERSON> could look at any triplet $x_i, x_j, x_k$ as well as $\overline{x_1},\overline{x_2},\overline{x_3}$. So presumably it's the conjunction of all those triplets when XORed together. All but one of these clauses can be satisfied. So the fraction is very close to one. But that's nowhere near the probability that <PERSON> will actually accept.
PS: We need a PCP tag. 768