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

CC BY-SA 4.0
2020-10-15T21:55:59.607Z
2020-10-15T21:55:59.607Z
Jason Gaitonde
<p>I am a mathematician working toward understanding a proof the the <strong>PCP</strong> theorem using Arora and Barak's textbook <em>Computational Complexity</em>. I believe I found a few (fixable) errors in Section 22.2, in the part titled &quot;Proving Theorem 11.5 from Lemma 22.4&quot;, but I am not sure I completely understand. As I stated <a href="https://cs.stackexchange.com/q/91963/88583">two years ago</a>, I still can't find any errata list that is very comprehensive.</p>
<p>I will copy their proof here (page 462 in my book) and then post my questions afterwards. Things I add are in brackets.</p>
<p>Note that I first posted this question <a href="https://cs.stackexchange.com/questions/130869/on-the-usage-of-arora-and-baraks-main-lemma-in-their-proof-of-the-pcp-theorem">here at cs.stackexchange</a> over a week ago and got no answers. I then <a href="https://cstheory.meta.stackexchange.com/questions/3061/is-this-question-about-the-pcp-theorem-appropriate-here">asked on meta</a> if it was appropriate for this site.</p>
<hr />
<p>Recall that for a <span class="math-container">$q_0$</span>CSP-instance <span class="math-container">$\varphi$</span>, we define <span class="math-container">$\operatorname{val}(\varphi)$</span> to be the maximum fraction of satisfiable constraints in <span class="math-container">$\varphi$</span>.</p>
<h2>Their proof:</h2>
<p><strong>Definition 22.3</strong> Let <span class="math-container">$f$</span> be a function mapping CSP instances to CSP instances. We say that <span class="math-container">$f$</span> is a CL-reduction (short for <em>complete linear-blowup reduction)</em> if it is polynomial-time computable and, for every CSP instance <span class="math-container">$\varphi$</span>, satisfies:</p>
<ul>
<li><em>Completeness:</em> If <span class="math-container">$\varphi$</span> is satisfiable then so is <span class="math-container">$f(\varphi)$</span></li>
<li><em>Linear blowup:</em> If <span class="math-container">$m$</span> is the number of constraints in <span class="math-container">$\varphi$</span>, then the new <span class="math-container">$q$</span>CSP instance <span class="math-container">$f(\varphi)$</span> has at most <span class="math-container">$Cm$</span> constraints and alphabet <span class="math-container">$W$</span>, where <span class="math-container">$C$</span> and <span class="math-container">$W$</span> can depend on the arity and the alphabet size of <span class="math-container">$\varphi$</span> (but not the number of constraints or variables).</li>
</ul>
<blockquote>
<p><strong>Lemma 22.4</strong> (<strong>PCP</strong> Main Lemma) There exist constants <span class="math-container">$q_0 \geq 3$</span>, <span class="math-container">$\epsilon_0 &gt; 0$</span>, and a CL-reduction <span class="math-container">$f$</span> such that for every <span class="math-container">$q_0$</span>CSP-instance <span class="math-container">$\varphi$</span> with binary alphabet, and every <span class="math-container">$\epsilon  &lt; \epsilon_0$</span> the instance <span class="math-container">$\psi = f(\varphi)$</span> is a <span class="math-container">$q_0$</span>CSP [instance] (over [a] binary alphabet) satisfying
<span class="math-container">$$ \operatorname{val}(\varphi) \leq 1 - \epsilon \implies \operatorname{val}(\psi) \leq 1 - 2\epsilon$$</span></p>
</blockquote>
<p><strong>Proving Theorem 11.5 from Lemma 22.4</strong>
Let <span class="math-container">$q_0 \geq 3$</span> [and <span class="math-container">$\epsilon_0 &gt; 0$</span>] be as stated in Lemma 22.4. As already observed, the decision problem <span class="math-container">$q_0$</span>CSP is <strong>NP</strong>-hard. To prove the <strong>PCP</strong> Theorem we give a reduction from this problem to GAP <span class="math-container">$q_0$</span>CSP. Let <span class="math-container">$\varphi$</span> be a <span class="math-container">$q_0$</span>CSP instance. Let <span class="math-container">$m$</span> be the number of constraints in <span class="math-container">$\varphi$</span>. If <span class="math-container">$\varphi$</span> is satisfiable, then <span class="math-container">$\operatorname{val}(\varphi) = 1$</span> and otherwise <span class="math-container">$\operatorname{val}(\varphi) \leq 1 - 1/m$</span>. We use Lemma 22.4 to amplify this gap [assuming <span class="math-container">$1/m$</span> isn't big enough]. Specifically, apply the function <span class="math-container">$f$</span> obtained by Lemma 22.4 to <span class="math-container">$\varphi$</span> a total of <span class="math-container">$\log m$</span> times. We get an instance <span class="math-container">$\psi$</span> such that if <span class="math-container">$\varphi$</span> is satisfiable, then so is <span class="math-container">$\psi$</span>, but if <span class="math-container">$\varphi$</span> is not satisfiable (and so <span class="math-container">$\operatorname{val}(\varphi) \leq 1 - 1/m$</span>), then <span class="math-container">$\operatorname{val}(\psi) \leq 1 - \min\{2\epsilon_0, 1 - 2^{\log m}/m \} = 1 - 2\epsilon_0$</span>. Note that the size of <span class="math-container">$\psi$</span> is at most <span class="math-container">$C^{\log m} m$</span>, which is polynomial in <span class="math-container">$m$</span>. Thus we have obtained a gap-preserving reduction from <span class="math-container">$L$</span> to the <span class="math-container">$(1-2\epsilon_0)$</span>-GAP <span class="math-container">$q_0$</span>CSP problem, and the <strong>PCP</strong> theorem is proved.</p>
<hr />
<h2>My questions:</h2>
<p>First I will ask about what I think is an easy typo, and this question leads to my next question.</p>
<blockquote>
<p>In the sentence beginning with &quot;We get an instance <span class="math-container">$\psi\ldots",$</span> instead of
<span class="math-container">$$\operatorname{val}(\psi) \leq 1 - \min\{2\epsilon_0, 1 - 2^{\log m}/m \} = 1 - 2\epsilon_0$$</span>
Don't they instead mean
<span class="math-container">$$\operatorname{val}(\psi) \leq \min\{1 - 2\epsilon_0, 1 - 2^{\log m}/m \} = 1 - 2\epsilon_0 ?$$</span></p>
</blockquote>
<p>I am assuming (and tried to confirm) that their logarithm is base 2.</p>
<p>Second, I don't buy that <span class="math-container">$\operatorname{val}(\psi) \leq \min\{1 - 2\epsilon_0, 1 - 2^{\log m}/m \}.$</span> In particular, they say &quot;apply the function <span class="math-container">$f$</span> obtained by Lemma 22.4 to <span class="math-container">$\varphi$</span> a total of <span class="math-container">$\log m$</span> times&quot;.</p>
<blockquote>
<p>Shouldn't they instead say, &quot;apply the function <span class="math-container">$f$</span> obtained by Lemma 22.4 to <span class="math-container">$\varphi$</span> up to a total <span class="math-container">$\log m$</span> times, until you get <span class="math-container">$\epsilon \geq \epsilon_0$</span>.&quot;?</p>
</blockquote>
<p>This is because applying Lemma 22.4 to <span class="math-container">$\varphi$</span> is only relevant if <span class="math-container">$\epsilon &lt; \epsilon_0.$</span></p>
<p>Next, assuming the answer to my last question is &quot;yes&quot;, then what if after applying the function <span class="math-container">$f$</span> zero or more times, we get an <span class="math-container">$\epsilon$</span> with <span class="math-container">$\epsilon = .51\epsilon_0$</span>? In that case, when we apply <span class="math-container">$f$</span> once more, we amplify the gap to <span class="math-container">$2\epsilon = 1.02\epsilon_0$</span>. In this case, we'd have  <span class="math-container">$\operatorname{val}(\psi) \leq 1 - 1.02\epsilon_0$</span>, in which case the lemma is no longer relevant. So I ask the next question:</p>
<blockquote>
<p>Doesn't the previous paragraph suggest that we only get <span class="math-container">$\operatorname{val}(\psi) \leq 1 - \epsilon_0$</span>?</p>
</blockquote>
<p>If this is the case, then I believe we can finish their proof by correcting their last sentence so that it says this: &quot;Thus we have obtained a gap-preserving reduction from <span class="math-container">$L$</span> to the <span class="math-container">$(1-\epsilon_0)$</span>-GAP <span class="math-container">$q_0$</span>CSP problem, and the <strong>PCP</strong> theorem is proved.&quot;</p>

<cc.complexity-theory>
On the usage of Arora and Barak's main lemma in their proof of the PCP theorem
Andrew Kelley
# On the usage of Arora and Barak's main lemma in their proof of the PCP theorem

(Asked by: username_0 on 2020-10-15)

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](https://cs.stackexchange.com/q/91963/88583), 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](https://cs.stackexchange.com/questions/130869/on-the-usage-of-arora-and-baraks-main-lemma-in-their-proof-of-the-pcp-theorem) over a week ago and got no answers. I then [asked on meta](https://cstheory.meta.stackexchange.com/questions/3061/is-this-question-about-the-pcp-theorem-appropriate-here) 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."

**Tags:** cc.complexity-theory


---

## 1 answers

### Answer by username_1 on 2020-10-15. Score: 8 | Accepted answer

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


---

