6
$\begingroup$

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 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}

$\endgroup$
4
  • 8
    $\begingroup$ 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! $\endgroup$
    – J.G
    Nov 5 '20 at 17:00
  • $\begingroup$ Did you write to Boaz Barak? $\endgroup$ Nov 7 '20 at 15:04
  • 1
    $\begingroup$ @Chekuri I wrote to them almost exactly a month ago about different things, and they haven't replied yet. $\endgroup$ Nov 7 '20 at 15:20
  • $\begingroup$ @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. $\endgroup$ Dec 22 '20 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.