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.
- 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.