<p>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.</p>
<p>In our case, we are interested in observing the (empirical) probability that PCP-verifiers give <span class="math-container">$yes$</span> answers when the word <span class="math-container">$x$</span> under consideration belongs to the target language <span class="math-container">$L$</span> but the certificate <span class="math-container">$\pi$</span> to be checked is not right. This probability is bounded by definition if <span class="math-container">$x\not\in L$</span> (e.g. <span class="math-container">$prob \leq \frac{1}{2}$</span>) or if <span class="math-container">$\pi$</span> is a correct certificate to prove <span class="math-container">$x\in L$</span> (<span class="math-container">$prob = 1$</span>), but it is not in that particular case. We wonder what the actual performance of PCP-verifiers is in that particular case.</p>
<p>Any paper reporting actual experiments running PCP-verifiers would also be a great lead.</p>

CC BY-SA 4.0
2022-07-30T21:58:43.863Z
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. https://github.com/lattice-based-zkSNARKs/lattice-zksnark/blob/master/lwe/snark/r1cs_lattice_snark_lpcp_tr.hpp
Yonatan N
CC BY-SA 4.0
2022-08-02T19:22:37.193Z
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](http://theory.cs.princeton.edu/complexity/book.pdf), 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.
EXPTIME-complete
<cc.complexity-theory><pcp><implementation>
Looking for an implementation of any PCP-verifier for any NP problem
EXPTIME-complete
# Looking for an implementation of any PCP-verifier for any NP problem

(Asked by: username_0 on 2022-07-30)

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.

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

> **Comments:**
> **username_1**: 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. https://github.com/lattice-based-zkSNARKs/lattice-zksnark/blob/master/lwe/snark/r1cs_lattice_snark_lpcp_tr.hpp  
> **username_0**: 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](http://theory.cs.princeton.edu/complexity/book.pdf), 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.  

---

## 0 answers

