Composition of Low-Error 2-Query PCPs Using Decodable PCPs
From MaRDI portal
Publication:5171197
DOI10.1109/FOCS.2009.8zbMath1292.68083OpenAlexW2130703751MaRDI QIDQ5171197
Publication date: 25 July 2014
Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/focs.2009.8
Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Decoding (94B35)
Related Items (8)
Low-degree test with polynomially small error ⋮ Derandomized parallel repetition via structured PCPs ⋮ Parallel Repetition of Two-Prover One-Round Games: An Exposition ⋮ Relaxed Locally Correctable Codes ⋮ Shorter arithmetization of nondeterministic computations ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Composition of Low-Error 2-Query PCPs Using Decodable PCPs ⋮ Short Locally Testable Codes and Proofs
This page was built for publication: Composition of Low-Error 2-Query PCPs Using Decodable PCPs
