I am working toward understanding a proof the the **PCP** theorem using Arora and Barak’s textbook *Computational Complexity*. I believe I found a few (fixable) errors in Section 22.2, in the part titled “Proving Theorem 11.5 from Lemma 22.4”, but I am not sure I completely understand. As I stated two years ago, I still can’t find any errata list that is very comprehensive.

I will copy their proof here (page 462 in my book) and then post my questions afterwards. Things I add are in brackets.

Recall that for a $q_0$CSP-instance $varphi$, we define $operatorname{val}(varphi)$ to be the maximum fraction of satisfiable constraints in $varphi$.

## Their proof:

**Definition 22.3** Let $f$ be a function mapping CSP instances to CSP instances. We say that $f$ is a CL-reduction (short for *complete linear-blowup reduction)* if it is polynomial-time computable and, for every CSP instance $varphi$, satisfies:

*Completeness:* If $varphi$ is satisfiable then so is $f(varphi)$
*Linear blowup:* If $m$ is the number of constraints in $varphi$, then the new $q$CSP instance $f(varphi)$ has at most $Cm$ constraints and alphabet $W$, where $C$ and $W$ can depend on the arity and the alphabet size of $varphi$ (but not the number of constraints or variables).

**Lemma 22.4** (**PCP** Main Lemma) There exist constants $q_0 geq 3$, $epsilon > 0$, and a CL-reduction $f$ such that for every $q_0$CSP-instance $varphi$ with binary alphabet, and every $epsilon < epsilon_0$ the instance $psi = f(varphi)$ is a $q_0$CSP (instance) (over (a) binary alphabet) satisfying

$$ operatorname{val}(varphi) leq 1 – epsilon implies operatorname{val}(psi) leq 1 – 2epsilon$$

**Proving Theorem 11.5 from Lemma 22.4**

Let $q_0 geq 3$ (and $epsilon_0 > 0$) be as stated in Lemma 22.4. As already observed, the decision problem $q_0$CSP is **NP**-hard. To prove the **PCP** Theorem we give a reduction from this problem to GAP $q_0$CSP. Let $varphi$ be a $q_0$CSP instance. Let $m$ be the number of constraints in $varphi$. If $varphi$ is satisfiable, then $operatorname{val}(varphi) = 1$ and otherwise $operatorname{val}(varphi) leq 1 – 1/m$. We use Lemma 22.4 to amplify this gap (assuming $1/m$ isn’t big enough). Specifically, apply the function $f$ obtained by Lemma 22.4 to $varphi$ a total of $log m$ times. We get an instance $psi$ such that if $varphi$ is satisfiable, then so is $psi$, but if $varphi$ is not satisfiable (and so $operatorname{val}(varphi) leq 1 – 1/m$), then $operatorname{val}(psi) leq 1 – min{2epsilon_0, 1 – 2^{log m}/m } = 1 – 2epsilon_0$. Note that the size of $psi$ is at most $C^{log m} m$, which is polynomial in $m$. Thus we have obtained a gap-preserving reduction from $L$ to the $(1-2epsilon_0)$-GAP $q_0$CSP problem, and the **PCP** theorem is proved.

## My questions:

First I will ask about what I think is an easy typo, and this question leads to my next question.

In the sentence beginning with “We get an instance $psildots”,$ instead of

$$operatorname{val}(psi) leq 1 – min{2epsilon_0, 1 – 2^{log m}/m } = 1 – 2epsilon_0$$

Don’t they instead mean

$$operatorname{val}(psi) leq min{1 – 2epsilon_0, 1 – 2^{log m}/m } = 1 – 2epsilon_0 ?$$

I am assuming (and tried to confirm) that their logarithm is base 2.

Second, I don’t buy that $operatorname{val}(psi) leq min{1 – 2epsilon_0, 1 – 2^{log m}/m }.$ In particular, they say “apply the function $f$ obtained by Lemma 22.4 to $varphi$ a total of $log m$ times”.

Shouldn’t they instead say, “apply the function $f$ obtained by Lemma 22.4 to $varphi$ up to a total $log m$ times, until you get $epsilon geq epsilon_0$.”?

This is because applying Lemma 22.4 to $varphi$ is only relevant if $epsilon < epsilon_0.$

Next, assuming the answer to my last question is “yes”, then what if after applying the function $f$ zero or more times, we get an $epsilon$ with $epsilon = .51epsilon_0$? In that case, when we apply $f$ once more, we amplify the gap to $2epsilon = 1.02epsilon_0$. In this case, we’d have $operatorname{val}(psi) leq 1 – 1.02epsilon_0$, in which case the lemma is no longer relevant. So I ask the next question:

Doesn’t the previous paragraph suggest that we only get $operatorname{val}(psi) leq 1 – epsilon_0$?

If this is the case, then I believe we can finish their proof by correcting their last sentence so that it says this: “Thus we have obtained a gap-preserving reduction from $L$ to the $(1-epsilon_0)$-GAP $q_0$CSP problem, and the **PCP** theorem is proved.”

If my interpretation is correct, then though I think these are mistakes in their proof, they don’t affect the proof, but rather, they were definitely confusing.