Are PCPs Inherent in Efficient Arguments? by Salil Vadhan, Harvard
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 poly logarithmic 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). Joint work with
Guy Rothblum.
Joanne Talbot Hanley
Last modified: Mon Aug 16 11:11:15 EDT 2010