Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.9
URN: urn:nbn:de:0030-drops-116949
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11694/
Ben-Eliezer, Omri ; Fischer, Eldar ; Levi, Amit ; Rothblum, Ron D.
Hard Properties with (Very) Short PCPPs and Their Applications
| pdf-format: |
|
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 ℓ, 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.
BibTeX - Entry
@InProceedings{beneliezer_et_al:LIPIcs:2020:11694,
author = {Omri Ben-Eliezer and Eldar Fischer and Amit Levi and Ron D. Rothblum},
title = {{Hard Properties with (Very) Short PCPPs and Their Applications}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {9:1--9:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11694},
URN = {urn:nbn:de:0030-drops-116949},
doi = {10.4230/LIPIcs.ITCS.2020.9},
annote = {Keywords: PCPP, Property testing, Tolerant testing, Erasure resilient testing, Randomized encoding, Coding theory}
}
| Keywords: | PCPP, Property testing, Tolerant testing, Erasure resilient testing, Randomized encoding, Coding theory | |
| Seminar: | 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 06.01.2020 |
