文章基本信息
- 标题：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
