Sound 3-query PCPPs are long

DOI10.1145/1595391.1595394MaRDI QIDQ5892181zbMATH OpenOpenAlexFDO

Authors Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah

Publication date 24 September 2015

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.228.213

zbMATH Keywords

PCP of proximityPCPP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Sound 3-Query PCPPs Are Long
• Robust PSPs of proximity, shorter PSPs and applications to coding
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Non-interactive proofs of proximity
• Small PCPs with low query complexity

Cited in

(7)

• Succinct non-interactive arguments via linear interactive proofs
• Combinatorial PCPs with short proofs
• Testing for forbidden posets in ordered rooted forests
• Relaxed locally correctable codes
• Relaxed locally correctable codes
• Sound 3-Query PCPPs Are Long
• A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification

This page was built for publication: Sound 3-query PCPPs are long

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