Approximating Satisfiable Satisfiability Problems.
To appear in Proceedings of the 5th European Conference on Algorithms, 1997.
Our approximation for satisfiable MAX 3CSP instances is better than any possible approximation for the unrestricted version of the problem. This result implies that the requirements of perfect completeness and non-adaptiveness weaken the acceptance power of PCP verifiers.
We also present the first non-trivial results about PCP classes defined in terms of free bits that collapse to P.