Abstract:

 A family of boolean functions on n variables, each of which depends on
 k variables, is epsilon-far from being satisfiable if one has to delete
 at least epsilon n^k of the functions to get a satisfiable family.
 We show that in order to test if a given family of such boolean
 functions is satisfiable, or is epsilon-far from being satisfiable,
 it suffices to consider the induced family on a randomly chosen set of
 c(k)/epsilon^2 variables. This can be extended to non-boolean variables,
 and has several applications to testing satisfiability and graph and
 hypergraph colorability.

 Joint work with Noga Alon (SODA 2002).