On Local versus Global Satisfiability.
Manuscript, March 1997.
We prove an extremal combinatorial result regarding the fraction of
satisfiable clauses in boolean CNF formulae enjoying a locally
checkable property, thus solving a problem that has been open for
We then generalize the problem to arbitrary constraint satisfaction
problems. We prove a tight result even in the generalized case.