Sound 3-Query PCPPs Are Long
ACM Transactions on Computation Theory · 2009
DOI: 10.1145/1595391.1595394 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2009. Verfasst von Eli Ben-Sasson und 3 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 48 Literaturangaben. Gefördert von: Israel Science Foundation.
Abstract (Originalsprache)
We initiate the study of the trade-off between the length of a probabilistically checkable proof of proximity (PCPP) and the maximal soundness that can be guaranteed by a 3-query verifier with oracle access to the proof. Our main observation is that a verifier limited to querying a short proof cannot obtain the same soundness as that obtained by a verifier querying a long proof. Moreover, we quantify the soundness deficiency as a function of the proof-length and show that any verifier obtaining “best possible” soundness must query an exponentially long proof. In terms of techniques, we focus on the special class of inspective verifiers that read at most 2 proof-bits per invocation. For such verifiers, we prove exponential length-soundness trade-offs that are later on used to imply our main results for the case of general (i.e., not necessarily inspective) verifiers. To prove the exponential trade-off for inspective verifiers, we show a connection between PCPP proof length and property-testing query complexity that may be of independent interest. The connection is that any linear property that can be verified with proofs of length ℓ by linear inspective verifiers must be testable with query complexity ≈ logℓ.
Förderung
- Israel Science Foundation
Zitieren
APA
Ben-Sasson, E., Harsha, P., Lachish, O., & Matsliah, A. (2009). Sound 3-Query PCPPs Are Long. ACM Transactions on Computation Theory. https://doi.org/10.1145/1595391.1595394
Vancouver
Ben-Sasson E, Harsha P, Lachish O, Matsliah A. Sound 3-Query PCPPs Are Long. ACM Transactions on Computation Theory. 2009. doi:10.1145/1595391.1595394
BibTeX
@article{BenSasson2009,
author = {Ben-Sasson, Eli and Harsha, Prahladh and Lachish, Oded and Matsliah, Arie},
title = {Sound 3-Query PCPPs Are Long},
journal = {ACM Transactions on Computation Theory},
year = {2009},
doi = {10.1145/1595391.1595394}
}
EUVIMED