2
$\begingroup$

I'm looking through some lectures and books to understand the PCP verifier constructed by Hastad. I noticed that the subtle difference of an adaptive or non-adaptive PCP verifier seems to correspond to verifier with perfect or non-perfect completeness.

In "A tight characterization of NP with 3 query PCPs" the authors point out that there are (due to Trevisan and Zwick) strong restrictions using non-adaptive PCPs, e.g. $$P = PCP_{1, \frac{5}{8} + \epsilon}(log(n), 3)$$ and they construct an adaptive PCP finally showing that $NP = PCP_{1, \frac{1}{2}+\epsilon}(log (n), 3)$.

Then again the definition in the textbook from Arora, Barak (and in other lectures) uses explicitly non-adaptive verifiers with perfect completeness (well, with soundness $\frac{1}{2}$).

Could someone give further explanations on this? Are different definitions with soundness paramter $\frac{1}{2}$ equivalent?

And one further question: Is it possible to construct a linear dictatorship test (as basis of the Hastad Verifier) which is complete AND non-adaptive?

Improve this question
$\endgroup$
2
  • $\begingroup$ Does the Arora-Barak definition you refer to use 3 queries, or a larger constant? $\endgroup$
    – Or Meir
    Commented Nov 1, 2014 at 21:10
  • $\begingroup$ The Hastad verifier in the book makes exactly 3 queries, is non-adaptive and has no full completeness. But with "definition" I meant the general definition of PCP verifiers, not specifically the Hastad verifier. $\endgroup$
    – SpaceMonkey
    Commented Nov 1, 2014 at 21:17

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.