Day 32

In this class we showed how MIP = NEXP implies lower bounds on approximating the clique problem and how this led to the PCP theorem. The PCP theorem states that every language in NP has  probabilistically checkable proof where the verifier uses O(log n) random bits and makes only a constant number of queries to a proof that just returns bit. Here is a strong version.

For any constant α > 7/8, there is a polynomial-time computable function f mapping 3-CNFs to 3-CNFs such that for all formula φ,

• If φ is satisfiable then f(φ) is satisfiable.
• If φ is not satisfiable then every assignment to f(φ) satisfies at most an α-fraction of the clauses.

The proof is an assignment, O(log n) random coins are used to pick a clause and only the 3-queries to the variables of that clause are needed.

We also talked about the Unique Games conjecture. 

Links:

• Interactive proofs and the hardness of approximating cliques by Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra and Mario Szegedy
• Proof verification and the hardness of approximation problems by Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan and Mario Szegedy. First proof of the PCP theorem.
• The PCP theorem by gap amplification by Irit Dinur. A simpler more combinatorial proof of the PCP theorem.
• Some optimal inapproximability results by Johan Håstad. Gets the tight result for 3-SAT above.
• On the power of unique 2-prover 1-round games by Subhash Khot. This paper introduces unique games.
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell
• Compendium of NP Optimization Problems. Good list of problems and their best known approximations and limitations.