The PCP theorem by gap amplification
From MaRDI portal
Publication:5891922
DOI10.1145/1132516.1132553zbMath1301.68133OpenAlexW2143112402MaRDI QIDQ5891922
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1132516.1132553
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On a class of optimization problems with no ``efficiently computable solution ⋮ ZK-PCPs from leakage-resilient secret sharing ⋮ A new line of attack on the dichotomy conjecture ⋮ On the derandomization of the graph test for homomorphism over groups ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ The tensor product of two good codes is not necessarily robustly testable ⋮ On the rectangle method in proofs of robustness of tensor products ⋮ Derandomized parallel repetition via structured PCPs ⋮ Combinatorial PCPs with efficient verifiers ⋮ Cones of multipowers and combinatorial optimization problems ⋮ Challenging epistemology: Interactive proofs and zero knowledge ⋮ Combinatorial algorithms for distributed graph coloring ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits ⋮ Short Locally Testable Codes and Proofs ⋮ Bravely, Moderately: A Common Theme in Four Recent Works ⋮ The PCP theorem for NP over the reals ⋮ Combinatorial PCPs with short proofs
