LCS Publication Details
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.