<p>I am a mathematician studying Arora and Barak's textbook <em>Computational Complexity</em>, and I am having trouble following one detail in their proof of this weaker <strong>PCP</strong> theorem:</p>
<blockquote>
<p><strong>Theorem 11.19.</strong> We have <strong>NP</strong> <span class="math-container">$\subseteq$</span> <strong>PCP</strong>(poly(<span class="math-container">$n$</span>), 1)</p>
</blockquote>
<p>Their proof makes sense other than the unexplained number 0.8 on page 253 in the last paragraph of the proof/section. (Besides that, I think there is another minor error.) I will sketch their proof below and give context to the question so that people without a copy of the book can follow.</p>
<blockquote>
<p>Where is their number 0.8 coming from? And should it instead be 0.501?</p>
</blockquote>
<p>Their online draft of the book is sufficiently different that I didn't find the 0.8 there (which in the draft, is in subsection 18.4.2 on page 367). My question is about their published version.</p>
<p>Of course, this question is different than <a href="https://cstheory.stackexchange.com/questions/47721/on-the-usage-of-arora-and-baraks-main-lemma-in-their-proof-of-the-pcp-theorem">the other question</a> I posted here a couple of weeks ago.</p>
<hr />
<h3>Sketch of their proof:</h3>
<p>Let QUADEQ denote the problem of given a set of quadratic equations over <span class="math-container">$\mathbb{F} = \mathbb{F}_2$</span>, to find out if it is satisfiable. This problem is <strong>NP</strong>-complete.</p>
<p>They show that QUADEQ has a <strong>PCP</strong> verifier using polynomialy many random bits and a constant number of queries.</p>
<p>A QUADEQ instance with <span class="math-container">$m$</span> equations and <span class="math-container">$n$</span> variables can be encoded as an <span class="math-container">$m \times n^2$</span> matrix <span class="math-container">$A$</span> and a vector <span class="math-container">$b$</span>. The task is to find out if there is a vector <span class="math-container">$\mathbf{u} \in \mathbb{F}^n$</span> such that letting <span class="math-container">$U = \mathbf{u} \otimes \mathbf{u}$</span>, we have <span class="math-container">$AU = b$</span>. Of course, <span class="math-container">$\mathbf{u} \otimes \mathbf{u}$</span> is flattened in a way to make <span class="math-container">$U$</span> a column vector (and consistent with the column indices of <span class="math-container">$A$</span>). The <span class="math-container">$i, j$</span> entry of <span class="math-container">$\mathbf{u} \otimes \mathbf{u}$</span> is by definition <span class="math-container">$u_i u_j$</span>.</p>
<p>The verifier <span class="math-container">$V$</span> expects a proof <span class="math-container">$\pi \in \{0, 1\}^{2^n + 2^{n^2}}$</span> to encode two functions <span class="math-container">$f \colon \mathbb{F}^n \to \mathbb{F}$</span> and <span class="math-container">$g \colon \mathbb{F}^{n^2} \to \mathbb{F}$</span>. In a correct proof, <span class="math-container">$f$</span> is the Walsh-Hadamard encoding for the satisfying assignment <span class="math-container">$\mathbf{u}$</span>. In other words, <span class="math-container">$f(\mathbf{x}) = \mathbf{x} \odot \mathbf{u}$</span>, where <span class="math-container">$\odot$</span> denotes the dot product (working mod 2). Also, in a correct proof <span class="math-container">$g$</span> is the Walsh-Hadamard encoding for the vector <span class="math-container">$\mathbf{u} \otimes \mathbf{u}$</span>. Hence, <span class="math-container">$f$</span> and <span class="math-container">$g$</span> are functionals (linear functions to <span class="math-container">$\mathbb{F}$</span>).</p>
<p>Here are the three steps in their proof:</p>
<blockquote>
<p>Step 1: Check that <span class="math-container">$f$</span> and <span class="math-container">$g$</span> are 0.999-close to linear functions.</p>
</blockquote>
<p>If they aren't, then reject the purported proof <span class="math-container">$\pi$</span>. If <span class="math-container">$f$</span> and <span class="math-container">$g$</span> are not 0.999-close to linear functions, then this step will fail with high probability. Suppose step 1 passes. Call the linear functions <span class="math-container">$\tilde{f}$</span> and <span class="math-container">$\tilde{g}$</span>. By local decoding, we can query <span class="math-container">$\tilde{f}$</span> (or <span class="math-container">$\tilde{g}$</span>) by making two queries to <span class="math-container">$f$</span> (or <span class="math-container">$g$</span>). Any query to <span class="math-container">$\tilde{f}$</span> will succeed with probability at least 0.998.</p>
<p>They state that Steps 2 and 3 of the proof &quot;will use a small (less than 20) number of queries to <span class="math-container">$\tilde{f}$</span>, <span class="math-container">$\tilde{g}$</span>.&quot;</p>
<blockquote>
<p>Side question: In the rest of the proof, don't they query <span class="math-container">$\tilde{f}$</span> exactly 20 times and <span class="math-container">$\tilde{g}$</span> exactly 11 times?</p>
</blockquote>
<p>Of course the 31 total queries is not less than 20, nor is 20 itself (in case they weren't summing the 20 and 11).</p>
<p>Regardless, they (still correctly) point out that &quot;with high probability (say <span class="math-container">$&gt; 0.9$</span>) local decoding will succeed on all these queries.&quot;</p>
<blockquote>
<p>Step 2: Let <span class="math-container">$\mathbf{u}$</span> be the vector encoded by <span class="math-container">$\tilde{f}$</span>. Verify that <span class="math-container">$\tilde{g}$</span> encodes <span class="math-container">$\mathbf{u} \otimes \mathbf{u}$</span>.</p>
</blockquote>
<p>This is done by doing the following test 10 independent times: &quot;Choose <span class="math-container">$\mathbf{r}, \mathbf{r}'$</span> independently at random from <span class="math-container">$\mathbb{F}^n$</span>, and if <span class="math-container">$\tilde{f}(\mathbf{r})\tilde{f}(\mathbf{r}') \neq \tilde{g}(\mathbf{r} \otimes \mathbf{r}')$</span> then halt and reject.&quot; (I will skip why this check works.) If <span class="math-container">$\tilde{g}$</span> doesn't encode <span class="math-container">$\mathbf{u} \otimes \mathbf{u}$</span>, then on any of the 10 trials, the verifier will reject <span class="math-container">$\pi$</span> with probability at least 1/4. In this case, it will reject <span class="math-container">$\pi$</span> with probability at least <span class="math-container">$1 - (3/4)^{10} &gt; 0.9$</span>.</p>
<p>Assume Step 2 passes.</p>
<blockquote>
<p>Step 3: Verify that <span class="math-container">$g$</span> encodes a satisfying assignment.</p>
</blockquote>
<p>This is done by making a random combination of the <span class="math-container">$m$</span> equations encoded by <span class="math-container">$A$</span> and <span class="math-container">$b$</span>. Then <span class="math-container">$\tilde{g}$</span> is queried once to check this new equation. If the instance <span class="math-container">$A$</span> and <span class="math-container">$b$</span> is not satisfied by <span class="math-container">$\mathbf{u}$</span>, then with probability at least 1/2, it won't satisfy this new equation.</p>
<p>In their conclusion, they state that if <span class="math-container">$A$</span>, <span class="math-container">$b$</span> is not satisfiable, then for all (necessarily incorrect) proofs <span class="math-container">$\pi$</span>, the verifier <span class="math-container">$V$</span> accepts <span class="math-container">$\pi$</span> with probability at most 0.8. Of course, <strong>if</strong> 0.8 ought to be 0.501, then 0.8 is true too, but I don't see any justifiable reason why the 0.8 is there.</p>
<hr />
<h3>How I got the number 0.501:</h3>
<p>Let <span class="math-container">$\pi$</span> be an incorrect proof of satisfiability for an unsatisfiable <span class="math-container">$A, b$</span>.  If <span class="math-container">$f$</span> and <span class="math-container">$g$</span> are not 0.999-close to linear functions, then <span class="math-container">$V$</span> rejects <span class="math-container">$\pi$</span> with high probability. So assume Step 1 passes. Also, if <span class="math-container">$\tilde{g}$</span> does not encode <span class="math-container">$\mathbf{u} \otimes \mathbf{u}$</span>, then <span class="math-container">$V$</span> rejects <span class="math-container">$\pi$</span> with probability greater than 0.9. So assume Step 2 passes.</p>
<p>Let <span class="math-container">$I$</span> be the event that <span class="math-container">$V$</span> acepts <span class="math-container">$\pi$</span>, and let <span class="math-container">$L$</span> be the event that local decoding of <span class="math-container">$\tilde{g}$</span> from <span class="math-container">$g$</span> in Step 3 works. Then <span class="math-container">$\text{Pr}(I) = \text{Pr}(I \cap L) + \text{Pr}(I \cap \overline{L}) = \text{Pr}(I | L)\text{Pr}(L) + \text{Pr}(I | \overline{L})\text{Pr}(\overline{L})$</span> which is bounded above by</p>
<p><span class="math-container">\begin{align}
(1/2)\text{Pr}(L) + \text{Pr}(\overline{L}) &amp;= (1/2)[\text{Pr}(L) + \text{Pr}(\overline{L}) + \text{Pr}(\overline{L})] \\
&amp;= 1/2 + (1/2)\text{Pr}(\overline{L}) \\
&amp;\leq 1/2 + (1/2)(1 - 0.998)\\
&amp;= 0.501
\end{align}</span></p>

CC BY-SA 4.0
2020-11-05T17:00:02.300Z
This is a good question, and if nobody answers I might take a closer look, but just a comment: I think many people would say that while AB is a really great resource and textbook, one probably ought take some of the finer details with a slight grain of salt. Some of this is typos and some of this is a slight nonchalance about numerical constants. But it’s good you’re reading very carefully!
Jason Gaitonde
CC BY-SA 4.0
2020-11-07T15:04:01.287Z
Did you write to Boaz Barak?
Chandra Chekuri
CC BY-SA 4.0
2020-11-07T15:20:33.417Z
@Chekuri I wrote to them almost exactly a month ago about different things, and they haven't replied yet.
Andrew Kelley
CC BY-SA 4.0
2020-12-22T03:21:11.127Z
@J.G So I emailed Arora and Barak a second time a month ago, and they haven't yet replied to that yet either. If you don't get to this no worries; I realize you don't get paid to help. The comment you already posted was helpful.
Andrew Kelley
<cc.complexity-theory>
On an unsubstantiated number in a proof of a weaker PCP theorem
Andrew Kelley
# On an unsubstantiated number in a proof of a weaker PCP theorem

(Asked by: username_0 on 2020-11-03)

I am a mathematician studying Arora and Barak's textbook *Computational Complexity*, and I am having trouble following one detail in their proof of this weaker **PCP** theorem:

> **Theorem 11.19.** We have **NP** $\subseteq$ **PCP**(poly($n$), 1)

Their proof makes sense other than the unexplained number 0.8 on page 253 in the last paragraph of the proof/section. (Besides that, I think there is another minor error.) I will sketch their proof below and give context to the question so that people without a copy of the book can follow.

> Where is their number 0.8 coming from? And should it instead be 0.501?

Their online draft of the book is sufficiently different that I didn't find the 0.8 there (which in the draft, is in subsection 18.4.2 on page 367). My question is about their published version.

Of course, this question is different than [the other question](https://cstheory.stackexchange.com/questions/47721/on-the-usage-of-arora-and-baraks-main-lemma-in-their-proof-of-the-pcp-theorem) I posted here a couple of weeks ago.

---

### Sketch of their proof:

Let QUADEQ denote the problem of given a set of quadratic equations over $\mathbb{F} = \mathbb{F}\_2$, to find out if it is satisfiable. This problem is **NP**-complete.

They show that QUADEQ has a **PCP** verifier using polynomialy many random bits and a constant number of queries.

A QUADEQ instance with $m$ equations and $n$ variables can be encoded as an $m \times n^2$ matrix $A$ and a vector $b$. The task is to find out if there is a vector $\mathbf{u} \in \mathbb{F}^n$ such that letting $U = \mathbf{u} \otimes \mathbf{u}$, we have $AU = b$. Of course, $\mathbf{u} \otimes \mathbf{u}$ is flattened in a way to make $U$ a column vector (and consistent with the column indices of $A$). The $i, j$ entry of $\mathbf{u} \otimes \mathbf{u}$ is by definition $u\_i u\_j$.

The verifier $V$ expects a proof $\pi \in \{0, 1\}^{2^n + 2^{n^2}}$ to encode two functions $f \colon \mathbb{F}^n \to \mathbb{F}$ and $g \colon \mathbb{F}^{n^2} \to \mathbb{F}$. In a correct proof, $f$ is the Walsh-Hadamard encoding for the satisfying assignment $\mathbf{u}$. In other words, $f(\mathbf{x}) = \mathbf{x} \odot \mathbf{u}$, where $\odot$ denotes the dot product (working mod 2). Also, in a correct proof $g$ is the Walsh-Hadamard encoding for the vector $\mathbf{u} \otimes \mathbf{u}$. Hence, $f$ and $g$ are functionals (linear functions to $\mathbb{F}$).

Here are the three steps in their proof:

> Step 1: Check that $f$ and $g$ are 0.999-close to linear functions.

If they aren't, then reject the purported proof $\pi$. If $f$ and $g$ are not 0.999-close to linear functions, then this step will fail with high probability. Suppose step 1 passes. Call the linear functions $\tilde{f}$ and $\tilde{g}$. By local decoding, we can query $\tilde{f}$ (or $\tilde{g}$) by making two queries to $f$ (or $g$). Any query to $\tilde{f}$ will succeed with probability at least 0.998.

They state that Steps 2 and 3 of the proof "will use a small (less than 20) number of queries to $\tilde{f}$, $\tilde{g}$."

> Side question: In the rest of the proof, don't they query $\tilde{f}$ exactly 20 times and $\tilde{g}$ exactly 11 times?

Of course the 31 total queries is not less than 20, nor is 20 itself (in case they weren't summing the 20 and 11).

Regardless, they (still correctly) point out that "with high probability (say $> 0.9$) local decoding will succeed on all these queries."

> Step 2: Let $\mathbf{u}$ be the vector encoded by $\tilde{f}$. Verify that $\tilde{g}$ encodes $\mathbf{u} \otimes \mathbf{u}$.

This is done by doing the following test 10 independent times: "Choose $\mathbf{r}, \mathbf{r}'$ independently at random from $\mathbb{F}^n$, and if $\tilde{f}(\mathbf{r})\tilde{f}(\mathbf{r}') \neq \tilde{g}(\mathbf{r} \otimes \mathbf{r}')$ then halt and reject." (I will skip why this check works.) If $\tilde{g}$ doesn't encode $\mathbf{u} \otimes \mathbf{u}$, then on any of the 10 trials, the verifier will reject $\pi$ with probability at least 1/4. In this case, it will reject $\pi$ with probability at least $1 - (3/4)^{10} > 0.9$.

Assume Step 2 passes.

> Step 3: Verify that $g$ encodes a satisfying assignment.

This is done by making a random combination of the $m$ equations encoded by $A$ and $b$. Then $\tilde{g}$ is queried once to check this new equation. If the instance $A$ and $b$ is not satisfied by $\mathbf{u}$, then with probability at least 1/2, it won't satisfy this new equation.

In their conclusion, they state that if $A$, $b$ is not satisfiable, then for all (necessarily incorrect) proofs $\pi$, the verifier $V$ accepts $\pi$ with probability at most 0.8. Of course, **if** 0.8 ought to be 0.501, then 0.8 is true too, but I don't see any justifiable reason why the 0.8 is there.

---

### How I got the number 0.501:

Let $\pi$ be an incorrect proof of satisfiability for an unsatisfiable $A, b$. If $f$ and $g$ are not 0.999-close to linear functions, then $V$ rejects $\pi$ with high probability. So assume Step 1 passes. Also, if $\tilde{g}$ does not encode $\mathbf{u} \otimes \mathbf{u}$, then $V$ rejects $\pi$ with probability greater than 0.9. So assume Step 2 passes.

Let $I$ be the event that $V$ acepts $\pi$, and let $L$ be the event that local decoding of $\tilde{g}$ from $g$ in Step 3 works. Then $\text{Pr}(I) = \text{Pr}(I \cap L) + \text{Pr}(I \cap \overline{L}) = \text{Pr}(I | L)\text{Pr}(L) + \text{Pr}(I | \overline{L})\text{Pr}(\overline{L})$ which is bounded above by

\begin{align}
(1/2)\text{Pr}(L) + \text{Pr}(\overline{L}) &= (1/2)[\text{Pr}(L) + \text{Pr}(\overline{L}) + \text{Pr}(\overline{L})] \\
&= 1/2 + (1/2)\text{Pr}(\overline{L}) \\
&\leq 1/2 + (1/2)(1 - 0.998)\\
&= 0.501
\end{align}

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: This is a good question, and if nobody answers I might take a closer look, but just a comment: I think many people would say that while AB is a really great resource and textbook, one probably ought take some of the finer details with a slight grain of salt. Some of this is typos and some of this is a slight nonchalance about numerical constants. But it’s good you’re reading very carefully!  
> **username_2**: Did you write to Boaz Barak?  
> **username_0**: @Chekuri I wrote to them almost exactly a month ago about different things, and they haven't replied yet.  
> **username_0**: @J.G So I emailed Arora and Barak a second time a month ago, and they haven't yet replied to that yet either. If you don't get to this no worries; I realize you don't get paid to help. The comment you already posted was helpful.  

---

## 0 answers

