Hard properties with (very) short PCPPs and their applications

Abstract

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$, we construct a property ${\mathcal{P}}^{(\ell )}\subseteq \{0,1{\}}^n$ satisfying the following: Any testing algorithm for ${\mathcal{P}}^{(\ell )}$ requires $\Omega (n)$ many queries, and yet ${\mathcal{P}}^{(\ell )}$ has a constant query PCPP whose proof size is $O(n\cdot {\log }^{(\ell )}n)$, where ${\log }^{(\ell )}$ denotes the $\ell$ times iterated log function (e.g., ${\log }^{(2)}n=\log \log n$). The best previously known upper bound on the PCPP proof size for a maximally hard to test property was $O(n\cdot \mathrm{poly}\log n)$. As an immediate application, we obtain stronger separations between the standard testing model and both the tolerant testing model and the erasure-resilient testing model: for every fixed $\ell$, we construct a property that has a constant-query tester, but requires $\Omega (n/{\log }^{(\ell )}(n))$ queries for every tolerant or erasure-resilient tester.