6
$\begingroup$

We all know the PCP Theorem. Is there any software package availalbe taking a CNF in e.g. DIMACS format as input, and producing a PCP encoding in the same format as output? It might be interesting to run existing SAT solvers on such encoded instances and compare the performance relative to plain instances.

$\endgroup$
5
$\begingroup$

There has been some recent effort to make PCPs practical for use in verifying outsourced computation. Check the work by this UT Austin group for example: http://www.cs.utexas.edu/pepper/.

$\endgroup$
2
  • $\begingroup$ (From what I can see, that work is "PCPs for succinct arguments" $\hspace{2.24 in}$ rather than "PCPs in their own right".) $\:$ $\endgroup$ – user6973 Aug 19 '13 at 22:20
  • $\begingroup$ succinct arguments are the goal of the work, i am not sure if they develop a general enough PCP encoder for OP's purposes on the way $\endgroup$ – Sasho Nikolov Aug 20 '13 at 4:05
5
$\begingroup$

Eli Ben-Sasson's group is working on implementing PCPs. You can e-mail him and ask for their code.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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