文章基本信息

标题：Hard Properties with (Very) Short PCPPs and Their Applications
本地全文：下载
作者：Omri Ben-Eliezer ; Eldar Fischer ; Amit Levi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：151
页码：1-27
DOI：10.4230/LIPIcs.ITCS.2020.9
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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^(â"")âS {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.
关键词：PCPP; Property testing; Tolerant testing; Erasure resilient testing; Randomized encoding; Coding theory