Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

Irit Dinur, Prahladh Harsha, Guy Kindler

We show that every language in NP has a PCP verifier that tosses $O(\log n)$ random coins, has perfect completeness, and a soundness error of at most $1/\text{poly}(n)$, while maki…