Towards an optimal query efficient PCP?
Subhash Khot, Muli Safra, Madhur Tulsiani · 2013
We construct a PCP based on the hyper-graph linearity test with 3 free queries. It has near-perfect completeness and soundness strictly less than 1/8. Such a PCP was known before only assuming the Unique Games Conjecture, albeit with soundness arbitrarily close to 1/16. At a technical level, our main contribution is constructing a new outer PCP which is "robust" against bounded degree polynomials, and showing that it can be composed with the hyper-graph linearity test with 3 free queries. We believe this outer PCP may be useful in obtaining the optimal query vs. soundness tradeoff for PCPs.