Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PCPP:
Reports tagged with pcpp:
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
verifier with oracle access to the proof. Our main observation is
that a verifier limited to querying a short ... more >>>

TR11-104 | 3rd August 2011
Or Meir

#### Combinatorial PCPs with efficient verifiers

Revisions: 3

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than ... more >>>

TR13-082 | 6th June 2013
Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

#### Some properties are not even partially testable

For a property $P$ and a sub-property $P'$, we say that $P$ is $P'$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $\epsilon$-far from $P$ by using $q$ queries. There are natural properties that require many queries to test, ... more >>>

TR13-134 | 25th September 2013
Or Meir

#### Combinatorial PCPs with Short Proofs

The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the ... more >>>

TR16-073 | 7th May 2016
Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

#### Improved concrete efficiency and security analysis of Reed-Solomon PCPPs

Revisions: 1 , Comments: 1

A Probabilistically Checkable Proof of Proximity (PCPP) for a linear code $C$, enables to determine very efficiently if a long input $x$, given as an oracle, belongs to $C$ or is far from $C$.
PCPPs are often a central component of constructions of Probabilistically Checkable Proofs (PCP)s [Babai et al. ... more >>>

TR16-149 | 23rd September 2016
Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev