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.

EDIT: This question was answered sufficiently at cstheory.stackexchange.

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

  • 1
    $\begingroup$ Papers often contain mistakes, and the same is true for textbooks. Most of them are annoying, but easy to correct. Some are fatal. $\endgroup$ Oct 6, 2020 at 7:36
  • $\begingroup$ I decided to ask at cstheory.stackexchange and received an answer there. $\endgroup$ Oct 15, 2020 at 22:19
  • 2
    $\begingroup$ I’m voting to close this question because it was answered on Theoretical Computer Science. $\endgroup$ Oct 16, 2020 at 7:24


Browse other questions tagged or ask your own question.