Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROOF-LENGTH:
Reports tagged with proof-length:
TR07-127 | 22nd November 2007
Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

#### Sound 3-query PCPPs are Long

We initiate the study of the tradeoff between the {\em length} of a
probabilistically checkable proof of proximity (PCPP) and the
maximal {\em soundness} that can be guaranteed by a $3$-query