L. Trevisan.<br>
<b>Approximating Satisfiable Satisfiability Problems.</b><br>
To appear in <i>Proceedings of the 5th European Conference
on Algorithms</i>, 1997.

<dl>


<dt> <b> Abstract </b> <dd> We
study the approximability of the Maximum Satisfiability Problem
and of Constraint Satisfaction Problems restricted to satisfiable
instances. For both problems we improve on the performance ratios
of known algorithms for the unrestricted case.

<p>

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.

<p>

We also present the first non-trivial results about PCP
classes defined in terms of free bits that collapse to P.

</dl>