Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

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/poly(n), while making O(poly log log n) queries into a proof over an alphabet of size at most n 1/poly log log n . Previous constructions that obtain 1/poly(n) soundness error used either poly log n queries or an exponential alphabet, i.e. of size 2 n c for some c> 0. Our result is an exponential improvement in both parameters simultaneously. Our result can be phrased as polynomial-gap hardness for approximate CSPs with arity poly log log n and alphabet size n 1/poly log n . The ultimate goal, in this direction, would be to prove polynomial hardness for CSPs with constant arity and polynomial alphabet size (aka the sliding scale conjecture for inverse polynomial soundness error).

Authors

• Irit Dinur
• Prahladh Harsha
• Guy Kindler

Keywords

• PCPs
• composition
• decodable PCPs
• sliding scale conjecture