Friday, November 10, 2017

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