Are PCPs inherent in efficient arguments?

DOI10.1007/S00037-010-0291-3MaRDI QIDQ626678zbMATH OpenOpenAlexFDO

Authors Guy N. Rothblum, Salil Vadhan

Publication date 18 February 2011

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL http://nrs.harvard.edu/urn-3:HUL.InstRepos:4854423

zbMATH Keywords

cryptographyprobabilistically checkable proofs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Recommendations

• Probabilistically Checkable Arguments
• scientific article; zbMATH DE number 1031001
• Universal Arguments and their Applications
• On the concrete efficiency of probabilistically-checkable proofs
• On Efficient Zero-Knowledge PCPs

Cited in

(8)

• Theory of Cryptography
• Sumcheck arguments and their applications
• Unprovable security of perfect NIZK and non-interactive non-malleable commitments
• Probabilistically Checkable Arguments
• Predictable arguments of knowledge
• Probabilistically checkable arguments for all NP
• Universal Arguments and their Applications
• Constructing tree decompositions of graphs with bounded gonality

This page was built for publication: Are PCPs inherent in efficient arguments?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q626678)