Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

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

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf

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