"Towards An Optimal Query Efficient PCP?""
Madhur Tulsiani
Toyota Technological Institute
Monday, April 23rd, 2012, 2:00 pm
EBU3B, Room 4140
Abstract
Hastad's celebrated PCP construction gives a PCP with 3 queries and soundness 1/2 i.e. it is a way of checking proofs for (say) SAT which accepts a valid proof of satisfiability for a satisfiable formula with probability 1-\epsilon and does not accept any proof for an unsatisfiable formula with probability more than 1/2 + \epsilon. It has been of considerable interest to characterize what is the optimal soundness which can be achieved with a k-query PCP. This question can equivalently be stated as determining the optimal hardness of approximation ratio for a k-variable (Boolean) Constraint Satisfaction Problem.
Optimal answers are known for this problem assuming the Unique Games Conjecture (UGC). We make some progress towards proving these results unconditionally. We construct a PCP based on the hyper-graph linearity test with 3 free queries (7 queries in total). 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. Previously, the only outer PCP for which this was known was Unique Label-Cover, which is conjectured to be hard by the UGC. We believe our outer PCP may be useful in obtaining the optimal query vs. soundness tradeoff for PCPs.
Joint work with Subhash Khot and Muli Safra.
Short biography
Madhur Tulsiani completed his bachelor’s in Computer Science at IIT Kanpur (2001-05) and a Ph.D. at UC Berkeley (2005-09) advised by Luca Trevisan. He also spent two years as a postdoc at the Institute for Advanced Study and Princeton University.