Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-109 | 31st August 2012 18:39

Towards An Optimal Query Efficient PCP?

RSS-Feed




TR12-109
Authors: Subhash Khot, Muli Safra, Madhur Tulsiani
Publication: 5th September 2012 11:06
Downloads: 1478
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint