<p>The query complexity used in this paper is <span class="math-container">$O(1)$</span> and <span class="math-container">$O(poly(logn))$</span>.</p>

<p>For Lemma 3.1 there is a note that the query complexity used is <span class="math-container">$O(1)$</span>.</p>

<p>If the question is how Lemma 3.1 generalizes to non-constant query complexity, this does present a problem outside of <span class="math-container">$O(poly(f(n)))$</span>.</p>

<p>This problem is sidestepped by composing a verifier that reduces query complexity to <span class="math-container">$O(1)$</span> (Lemma 4.4).</p>

CC BY-SA 4.0
2019-05-25T13:23:01.140Z
2019-05-25T21:38:37.093Z
2019-05-25T21:38:37.093Z
Lem n
<p>I am reading the proof from <a href="https://www.cs.princeton.edu/~arora/pubs/thesis.pdf" rel="nofollow noreferrer">here</a> and I stumbled upon a technical (yet crucial) problem. I know this is rather specific and the context is problematic, but I couldn't figure it out myself.</p>

<p>In pages 51 and 55, after presenting the "standard" verifiers, they turn to modify the verifiers in order to check split assignments.</p>

<p>In the first case (p. 51) they check that <span class="math-container">$f_1,\dots,f_k$</span> are <span class="math-container">$0.01$</span>-close to the polynomial code, and then they use the Algebraization (+Zero-Testers) to construct a family of polynomials (with a Sum-Check property related to the input formula) that each can be evaluated at a point given 3 values of each of <span class="math-container">$\widetilde{f}_1,\dots,\widetilde{f}_k$</span> (the codewords of the polynomial code closet to <span class="math-container">$f_1,\dots,f_k$</span>).</p>

<p>In the second case (p. 55) they check that <span class="math-container">$f_1,\dots,f_k$</span> are <span class="math-container">$0.01$</span>-close to being linear, and then they define a function <span class="math-container">$f$</span> to be a special sum of <span class="math-container">$\widetilde{f}_1,\dots,\widetilde{f}_k$</span> such that <span class="math-container">$f$</span> can be evaluated at a point given values of each of <span class="math-container">$\widetilde{f}_1,\dots,\widetilde{f}_k$</span> (the linear functions closet to <span class="math-container">$f_1,\dots,f_k$</span>).</p>

<p>Then in both cases they perform tests (Sum-Check or Tensor + Hadamard) on the values of a random polynomial in the family / <span class="math-container">$\widetilde{f}$</span>.</p>

<p>My problem is that the procedure for reconstruction of the required values of each of <span class="math-container">$\widetilde{f}_i$</span> can provide incorrect values with some <strong>non-negligible constant probability</strong>. Moreover, the probability that all the values are reconstructed correctly is very low, only <span class="math-container">$c^k$</span> for some constant <span class="math-container">$c$</span>. And this is true for both cases. </p>

<p>This can be bad as some of the steps of the verifiers require to obtain values of the target function <span class="math-container">$f$</span> / a polynomial from the family w.h.p.</p>

<p>So, we need to amplify the success probability by repeatedly using the "reconstruction algebraic procedure" some <span class="math-container">$O(\log k)$</span> times for each <span class="math-container">$\widetilde{f}_i$</span>. </p>

<p>Now, this means that the blow-up in the query complexity of the sub-routine (relatively to the query complexity of the original verifiers) is slightly larger than <span class="math-container">$k$</span>, i.e. it is <span class="math-container">$O(k\log k)$</span> (in contrast to the "guaranteed"-"desired" <span class="math-container">$O(k)$</span> blowup in the statement of the theorems). </p>

<p>Is this a problem or am I missing something (which I probably am)?</p>

CC BY-SA 4.0
2019-05-25T18:53:13.807Z
Sorry if that should be obvious, but where is the statement of the theorems asking for a $O(k)$ blowup? Based on a cursory reading, $k$ seems to be any fixed constant integer (isn't it?).
Clement C.
CC BY-SA 4.0
2019-05-25T19:26:51.283Z
@ClementC. Look at the definitions numbered 3.2 and 3.3 combined with the composition recursion lemma afterwards (and most crucially its proof). Observe that the only place where the normal form verifier's ability to check split assignments is used is in the proof of the composition lemma (in fact, in any other place it is a "great liability" to deal with, when constructing verifiers). There, in the proof, $k$ is **not** a constant at all.
Don Fanucci
CC BY-SA 4.0
2019-05-25T21:43:18.737Z
Fair, it's used for $p=Q(n)$. For the use in proving the PCP theorem in Corollary 3.3 and Theorem 3.5, though, $Q(n)=1$, so (regardless of whether that extra $\log k$ should indeed be here or not) that's indeed a constant.
Clement C.
CC BY-SA 4.0
2019-05-26T05:28:40.570Z
@ClementC. Thanks, you are correct that when we use composition we use a constant $p$.
Don Fanucci
<cc.complexity-theory><pcp>
Technical issue with PCP theorem proof
Don Fanucci
# Technical issue with PCP theorem proof

(Asked by: username_0 on 2019-04-27)

I am reading the proof from [here](https://www.cs.princeton.edu/~arora/pubs/thesis.pdf) and I stumbled upon a technical (yet crucial) problem. I know this is rather specific and the context is problematic, but I couldn't figure it out myself.

In pages 51 and 55, after presenting the "standard" verifiers, they turn to modify the verifiers in order to check split assignments.

In the first case (p. 51) they check that $f\_1,\dots,f\_k$ are $0.01$-close to the polynomial code, and then they use the Algebraization (+Zero-Testers) to construct a family of polynomials (with a Sum-Check property related to the input formula) that each can be evaluated at a point given 3 values of each of $\widetilde{f}\_1,\dots,\widetilde{f}\_k$ (the codewords of the polynomial code closet to $f\_1,\dots,f\_k$).

In the second case (p. 55) they check that $f\_1,\dots,f\_k$ are $0.01$-close to being linear, and then they define a function $f$ to be a special sum of $\widetilde{f}\_1,\dots,\widetilde{f}\_k$ such that $f$ can be evaluated at a point given values of each of $\widetilde{f}\_1,\dots,\widetilde{f}\_k$ (the linear functions closet to $f\_1,\dots,f\_k$).

Then in both cases they perform tests (Sum-Check or Tensor + Hadamard) on the values of a random polynomial in the family / $\widetilde{f}$.

My problem is that the procedure for reconstruction of the required values of each of $\widetilde{f}\_i$ can provide incorrect values with some **non-negligible constant probability**. Moreover, the probability that all the values are reconstructed correctly is very low, only $c^k$ for some constant $c$. And this is true for both cases.

This can be bad as some of the steps of the verifiers require to obtain values of the target function $f$ / a polynomial from the family w.h.p.

So, we need to amplify the success probability by repeatedly using the "reconstruction algebraic procedure" some $O(\log k)$ times for each $\widetilde{f}\_i$.

Now, this means that the blow-up in the query complexity of the sub-routine (relatively to the query complexity of the original verifiers) is slightly larger than $k$, i.e. it is $O(k\log k)$ (in contrast to the "guaranteed"-"desired" $O(k)$ blowup in the statement of the theorems).

Is this a problem or am I missing something (which I probably am)?

**Tags:** cc.complexity-theory, pcp

> **Comments:**
> **username_1**: Sorry if that should be obvious, but where is the statement of the theorems asking for a $O(k)$ blowup? Based on a cursory reading, $k$ seems to be any fixed constant integer (isn't it?).  
> **username_0**: @ClementC. Look at the definitions numbered 3.2 and 3.3 combined with the composition recursion lemma afterwards (and most crucially its proof). Observe that the only place where the normal form verifier's ability to check split assignments is used is in the proof of the composition lemma (in fact, in any other place it is a "great liability" to deal with, when constructing verifiers). There, in the proof, $k$ is **not** a constant at all.  
> **username_1**: Fair, it's used for $p=Q(n)$. For the use in proving the PCP theorem in Corollary 3.3 and Theorem 3.5, though, $Q(n)=1$, so (regardless of whether that extra $\log k$ should indeed be here or not) that's indeed a constant.  
> **username_0**: @ClementC. Thanks, you are correct that when we use composition we use a constant $p$.  

---

## 1 answers

### Answer by username_2 on 2019-05-25. Score: 1

The query complexity used in this paper is $O(1)$ and $O(poly(logn))$.

For Lemma 3.1 there is a note that the query complexity used is $O(1)$.

If the question is how Lemma 3.1 generalizes to non-constant query complexity, this does present a problem outside of $O(poly(f(n)))$.

This problem is sidestepped by composing a verifier that reduces query complexity to $O(1)$ (Lemma 4.4).


---

