Some optimal inapproximability results

Abstract:

Using very efficient probabilistically checkable proofs (PCP) for NP we prove that unless NP=P, some simple approximation algorithms for basic NP-hard optimization problems are essentially optimal. In particular given a SAT formula with exactly 3 variables in each clause it is not hard to find an assignment that satisfies a fraction 7/8 of the clauses. We prove that (upto an arbitrary epsilon > 0) this is the best possible for a polynomial time approximation algorithm.

In this talk we concentrate on the problem of given a linear system of equations mod 2, to satisfy the maximal number of equations. This problem is easy to approximate within a factor of 2 and we prove that this is essentially tight. This result is obtained by constructing a PCP that uses logarithmic randomness, reads 3 bits in the proof and accepts based on the exclusive-or of the these bits. This proof system has completeness 1-epsilon and soundness 1/2+epsilon, for any constant epsilon > 0.