Hard properties with (very) short PCPPs and their applications

Omri Ben-Eliezer, Eldar Fischer, Amit Levi +1

We show that there exist properties that are maximally hard for testing, while still admitting PCPPs with a proof size very close to linear. Specifically, for every fixed $\ell$, w…