Show simple item record

dc.contributor.authorRothblum, Guy N.
dc.contributor.authorVadhan, Salil P.
dc.date.accessioned2011-04-18T19:03:33Z
dc.date.issued2009
dc.identifier.citationRothblum, Guy N., and Salil Vadhan. 2009. Are PCPs inherent in efficient arguments? Electronic Colloquium on Computational Complexity TR09-089.en_US
dc.identifier.issn1433-8092en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4854423
dc.description.abstractStarting 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).en_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherHasso-Plattner-Institut fuer Softwaresystemtechnik GmbHen_US
dc.relation.isversionofhttp://eccc.hpi-web.de/report/2009/089/en_US
dc.relation.hasversionhttp://people.seas.harvard.edu/~salil/research/ArgPCP-ccc09.pdfen_US
dc.relation.hasversionhttp://people.seas.harvard.edu/~salil/research/ArgPCP-cc.pdfen_US
dc.relation.hasversionhttp://people.seas.harvard.edu/~salil/research/ArgPCP-sep09.pdfen_US
dash.licenseLAA
dc.subjectPCPen_US
dc.subjectCS Proofsen_US
dc.subjectargument systemsen_US
dc.titleAre PCPs Inherent in Efficient Arguments?en_US
dc.typeJournal Articleen_US
dc.description.versionVersion of Recorden_US
dc.relation.journalElectronic Colloquium on Computational Complexityen_US
dash.depositing.authorVadhan, Salil P.
dc.date.available2011-04-18T19:03:33Z
dc.identifier.doi10.1109/CCC.2009.40
dash.contributor.affiliatedVadhan, Salil


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record