How does the strong form of the PCP theorem imply the inapproximability of Max-XORSAT?

Question

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 Arthur 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 Arthur could look at, we get a system of linear equations mod 2. If Merlin takes his best shot at a proof, the probability that Arthur 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. Merlin could just make Arthur 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 Arthur computes along the way.

Further, It's not a priori clear to me that Arthur 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 Arthur accepts with probability less than $1/2+\delta$?

Let's take a degenerate case as an example. Arthur asks Merlin 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 Arthur clearly doesn't need Merlin's help. But he can go out of his way to use it anyway. Here's what they do:
First Merlin gives Arthur a PCP $\mathbf{x} \in \{0,1\}^n$ (let's assume $n \gg 3$). Then Arthur checks if $\mathbf{b=1}.$ If it is, he checks that $x_1 \oplus x_2 \oplus x_3 = 1$ holds in Merlin'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.
Merlin can thus convince Arthur 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 Arthur 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, Arthur 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 Arthur will actually accept.

PS: We need a PCP tag.

Answer 1

Theorem 11.4 states that for every $\delta > 0$ there is a polytime computable function that on input $\varphi$ outputs a PCP (of a certain form) such that (i) if $\varphi$ is satisfiable then the cost of the PCP (to be defined) is at least $1-\delta$, and (ii) if $\varphi$ is unsatisfiable then the cost of the PCP is at most $1/2+\delta$.

The PCP consists of a distribution over quadruples $(i,j,k,b)$ where $i,j,k$ are indices in the range $1,\ldots,N$, for some $N$ depending polynomially on the size of $\varphi$, and $b \in \{0,1\}$. The value of an assignment $\alpha\colon \{1,\ldots,N\} \to \{0,1\}$ is equal to $\Pr[\alpha(i) \oplus \alpha(j) \oplus \alpha(k) = b]$, and the value of the PCP is the maximum value of an assignment.

(The version in which $b = 0$ always is easy to solve – the zero assignment has value 1. Similarly, when $b = 1$ the one assignment has value 1.)

Furthermore, the distribution is generated using $t = O(\log n)$ random bits. We can think of $i,j,k,b$ as functions of the randomness $r$.

Consider now the MAX-XORSAT instance $$ \bigwedge_{r \in \{0,1\}^t} (x_{i(r)} \oplus x_{j(r)} \oplus x_{k(r)} = b(r)). $$ Since $|\{0,1\}^t| = 2^t = 2^{O(\log n)} = \mathit{poly}(n)$, this instance has size polynomial in the size of $\varphi$.

The maximum fraction of constraints satisfied by this MAX-XORSAT instance is exactly the same as the value of the PCP. Hence if $\varphi$ is satisfiable, at least a $1-\delta$ fraction of constraints can be satisfied, whereas if $\varphi$ is unsatisfiable, at most a $1/2+\delta$ fraction can be satisfied.

An approximation algorithm for MAX-XORSAT with ratio strictly better than $1/2$ can distinguish between the two cases (for small enough $\delta$), and so can find out whether $\varphi$ is satisfiable or not. In other words, such an algorithm can be used to solve SAT.