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 >>>

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are \delta-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are \delta-close to the property. In particular, no set ... more >>>