Composition of Low-Error 2-Query PCPs Using Decodable PCPs

DOI10.1137/100788161zbMath1290.68046OpenAlexW2125632628MaRDI QIDQ5408773

Irit Dinur, Prahladh Harsha

Publication date: 11 April 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/100788161

zbMATH Keywords

compositionprobabilistically checkable proofsPCPlocally decodablelow soundness error

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ Unnamed Item ⋮ Hardness results for approximate pure Horn CNF formulae minimization ⋮ Smooth and strong PCPs ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

This page was built for publication: Composition of Low-Error 2-Query PCPs Using Decodable PCPs