1
$\begingroup$

Is there any implementation of any PCP-verifier (for any NP problem) researchers can download and test? No matter if it is a github entry with actual downloadable code or just a (reasonably detailed) pseudocode description. That code can be extracted by a careful examination of the proof of the PCP theorem, but writing it fully from scratch seems like a cumbersome and redundant task for anyone interested in playing with it. We don't mind if it is the Hastad's 3-bit version or any other else.

In our case, we are interested in observing the (empirical) probability that PCP-verifiers give $yes$ answers when the word $x$ under consideration belongs to the target language $L$ but the certificate $\pi$ to be checked is not right. This probability is bounded by definition if $x\not\in L$ (e.g. $prob \leq \frac{1}{2}$) or if $\pi$ is a correct certificate to prove $x\in L$ ($prob = 1$), but it is not in that particular case. We wonder what the actual performance of PCP-verifiers is in that particular case.

Any paper reporting actual experiments running PCP-verifiers would also be a great lead.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ You can probably find implementations in the context of (certain classes of) SNARKs. E.g. this package claims to contain an implementation, but I haven't made any attempt to verify its correctness. github.com/lattice-based-zkSNARKs/lattice-zksnark/blob/master/… $\endgroup$
    – Yonatan N
    Jul 30, 2022 at 21:58
  • $\begingroup$ Thanks for your reply, but we are looking for an implementation of a PCP-verifier as the ones taken in PCP theorems, e.g. see the definition of PCP-verifier ((r,q)-verifier) in Arora & Barak's book, Definition 18.1, or in particular, the Hastad's 3-bit version, introduced in Theorem 19.5. The verifiers implemented for zkSNARKS do not fit into that definition, and we do not see how they could be transformed into the kind of verifier we need. $\endgroup$
    – EXPTIME-complete
    Aug 2, 2022 at 19:22

0

Reset to default

Your Answer

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