# Are PCPs Inherent in Efficient Arguments?

Guy Rothblum and Salil Vadhan

### 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).

### Versions

- In
*Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC `09),* pages 81-92, 15-18 July 2009. [pdf][IEEE page][slides]
*Electronic Colloquium on Computational Complexity, *Technical Report TR09-089, October 2009. [pdf][ECCC page]
*Computational Complexity *19(2), pages 265-304. Special Issue on CCC `09, May 2010. [pdf][Birkhauser page]

[ back to
Salil Vadhan's research]