| Publication Title: |
Implementing Probabilistically Checkable Proofs of Proximity |
| Publication Author: |
Bhattacharyya, Arnab |
| Additional Authors: |
|
| LCS Document Number: |
MIT-LCS-TR-998 |
| Publication Date: |
8-8-2005 |
| LCS Group: |
Complexity Theory |
| Additional URL: |
|
| Abstract: |
| Abstract: In this paper, we describe a proof-of-concept implementation of the probabilistically checkable proof of proximity (PCPP) system described by Ben-Sasson and Sudan in \\cite{bs05}. In particular, we implement a PCPP prover and verifier for Reed-Solomon codes; the prover converts an evaluation of a polynomial on a linear set into a valid PCPP, while the verifier queries the evaluation and the PCPP to check that the evaluation is close to a Reed-Solomon codeword. We prove tight bounds on the various parameters associated with the prover and verifier and describe some interesting programmatic issues that arise during their implementation. |
| To obtain this publication: |
|
|
|
To purchase a printed copy of this publication please contact
MIT
Document Services.
|