2026-07-23T04:27:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11694 2024-03-06T10:48:28Z ddc:004 open_access

Hard Properties with (Very) Short PCPPs and Their Applications Ben-Eliezer, Omri Fischer, Eldar Levi, Amit Rothblum, Ron D. PCPP Property testing Tolerant testing Erasure resilient testing Randomized encoding Coding theory 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⋅polylog(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 ℓ, we construct a property that has a constant-query tester, but requires Ω(n/log^(ℓ)(n)) queries for every tolerant or erasure-resilient tester. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Omri Ben-Eliezer and Eldar Fischer and Amit Levi and Ron D. Rothblum 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.9 urn:nbn:de:0030-drops-116949 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.9 eng https://creativecommons.org/licenses/by/3.0/legalcode