12
$\begingroup$

I am reading the proof from here 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)?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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?). $\endgroup$
    – Clement C.
    Commented May 25, 2019 at 18:53
  • $\begingroup$ @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. $\endgroup$
    – Don Fanucci
    Commented May 25, 2019 at 19:26
  • $\begingroup$ 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. $\endgroup$
    – Clement C.
    Commented May 25, 2019 at 21:43
  • $\begingroup$ @ClementC. Thanks, you are correct that when we use composition we use a constant $p$. $\endgroup$
    – Don Fanucci
    Commented May 26, 2019 at 5:28

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.