2019/09/07 by Ben-Eliezer, Omri, Fischer, Eldar, Levi, Amit +1
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1909.03255
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 ℓ, we construct a property P(ℓ)⊆\0,1\n satisfying the following: Any testing algorithm for P(ℓ) requires Ω(n) many queries, and yet P(ℓ) has a constant query PCPP whose proof size is O(n⋅ log(ℓ)n), where log(ℓ) denotes the ℓ 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 ⋅ polylogn). 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 ℓ, we construct a property that has a constant-query tester, but requires Ω(n/log(ℓ)(n)) queries for every tolerant or erasure-resilient tester.