# On the usage of Arora and Barak's main lemma in their proof of the PCP theorem

I am a mathematician 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.

Note that I first posted this question here at cs.stackexchange over a week ago and got no answers. I then asked on meta if it was appropriate for this site.

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 > 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 - 2\epsilon$$

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\{2\epsilon_0, 1 - 2^{\log m}/m \} = 1 - 2\epsilon_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-2\epsilon_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 $$\psi\ldots",$$ instead of $$\operatorname{val}(\psi) \leq 1 - \min\{2\epsilon_0, 1 - 2^{\log m}/m \} = 1 - 2\epsilon_0$$ Don't they instead mean $$\operatorname{val}(\psi) \leq \min\{1 - 2\epsilon_0, 1 - 2^{\log m}/m \} = 1 - 2\epsilon_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 - 2\epsilon_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 = .51\epsilon_0$$? In that case, when we apply $$f$$ once more, we amplify the gap to $$2\epsilon = 1.02\epsilon_0$$. In this case, we'd have $$\operatorname{val}(\psi) \leq 1 - 1.02\epsilon_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."

I think the authors are actually fine on the other two questions. Imagine you've applied $$f$$ exactly $$\log_2 m$$ times and that $$\varphi$$ was unsatisfiable. At some first time $$k<\log_2 m$$, you know $$\text{val}(f^{(k)}(\varphi))\leq 1-\epsilon_0$$ because you double the gap while the value is at least $$1-\epsilon_0$$ because of the Lemma, and certainly this can't happen $$\log_2 m$$ times. Applying the lemma once more, it is true that $$\text{val}(f^{(k+1)}(\varphi))\leq 1-2\epsilon_0$$, because even if the previous gap was much bigger than $$\epsilon_0$$, note that the Lemma does not say you double the true gap of $$f^{(k)}(\varphi)$$ by applying $$f$$ again. Rather, it says you can ensure the new gap is at least twice any lower bound on the current gap that is not more than $$\epsilon_0$$. Because $$\epsilon_0$$ is such a lower bound, you get the stated claim. This applies for $$k+1,\ldots,\log_2 m$$. In other words, you may or may not make any more progress by continuing to apply $$f$$, but you will be at most $$1-2\epsilon_0$$.