Publication: Are PCPs Inherent in Efficient Arguments?
Open/View Files
Date
2009
Authors
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
Hasso-Plattner-Institut fuer Softwaresystemtechnik GmbH
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Rothblum, Guy N., and Salil Vadhan. 2009. Are PCPs inherent in efficient arguments? Electronic Colloquium on Computational Complexity TR09-089.
Research Data
Abstract
Starting with Kilian (STOC ‘92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound proofs), for example with polylogarithmic communication complexity. Ishai et al. (CCC ‘07) raised the question of whether PCPs are inherent in efficient arguments, and to what extent. We give evidence that they are, by showing how to convert any argument system whose soundness is reducible to the security of some cryptographic primitive into a PCP system whose efficiency is related to that of the argument system and the reduction (under certain complexity assumptions).
Description
Keywords
PCP, CS Proofs, argument systems
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service