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

Question

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."

Answer 1

I think you're right about the first typo.

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$.