Are PCPs Inherent in Efficient Arguments?

DSpace/Manakin Repository

Are PCPs Inherent in Efficient Arguments?

Citable link to this page

. . . . . .

Title: Are PCPs Inherent in Efficient Arguments?
Author: Rothblum, Guy N.; Vadhan, Salil P.

Note: Order does not necessarily reflect citation order of authors.

Citation: Rothblum, Guy N., and Salil Vadhan. 2009. Are PCPs inherent in efficient arguments? Electronic Colloquium on Computational Complexity TR09-089.
Full Text & Related Files:
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).
Published Version: http://eccc.hpi-web.de/report/2009/089/
Other Sources: http://people.seas.harvard.edu/~salil/research/ArgPCP-ccc09.pdf
http://people.seas.harvard.edu/~salil/research/ArgPCP-cc.pdf
http://people.seas.harvard.edu/~salil/research/ArgPCP-sep09.pdf
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4854423

Show full Dublin Core record

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7078]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
 
 

Search DASH


Advanced Search
 
 

Submitters