Random sampling and approximation of MAX-CSPs

In a maximum-r-constraint satisfaction problem with variables {x₁,x₂,...,x_n}, we are given Boolean functions f₁,f₂,...,f_m each involving r of the n variables and are to find the maximum number of these functions that can be made true by a truth assignment to the variables. We show that for r fixed, there is an integer q ∈ O(log(1/ε)/ε⁴) such that if we choose q variables (uniformly) at random, the answer to the sub-problem induced on the chosen variables is, with high probability, within an additive error of εq^r of q^r/n^r times the answer to the original n-variable problem. The previous best result for the case of r = 2 (which includes many graph problems) was that there is an algorithm which given the induced sub-problem on q = O(1/ε⁵) variables, can find an approximation to the answer to the whole problem within additive error εn². For r ≥ 3, the conference version of this paper (in: Proceedings of the 34th ACM STOC, ACM, New York, 2002, pp. 232-239) and independently Andersson and Engebretsen give the first results with sample complexity q dependent only polynomially upon 1/ε. Their algorithm has a sample complexity q of O(1/ε⁷). They (as also the earlier papers) however do not directly prove any relation between the answer to the sub-problem and the whole problem as we do here. Our method also differs from other results in that it is linear algebraic, rather than combinatorial in nature.