PCP characterizations of NP

DOI10.1145/301250.301265zbMath1346.68096OpenAlexW2078090052MaRDI QIDQ2819531

Eldar Fischer, Ran Raz, Irit Dinur, Guy Kindler, Shmuel Safra

Publication date: 29 September 2016

Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/301250.301265

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Testing juntas ⋮ Composition of Low-Error 2-Query PCPs Using Decodable PCPs ⋮ On the hardness of approximating label-cover ⋮ Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard

This page was built for publication: PCP characterizations of NP