Random sampling and approximation of MAX-CSPs

In a maximum-r-constraint satisfaction problem with variables {x(1), x(2),...,x(n)}, we are given Boolean functions f(1),f(2),...,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 is an element of O(log(1epsilon)/epsilon(4)) such that if we choose q variables (uniformly) at random, the answer to the subproblem induced on the chosen variables is, with high probability, within an additive error of epsilonq(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/epsilon(5)) variables, can find an approximation to the answer to the whole problem within additive error epsilonn(2). For rgreater than or equal to3, 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 polynormally upon 1/epsilon. Their algorithm has a sample complexity q of O(1/epsilon(7)). 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. (C) 2003 Elsevier Science (USA). All rights reserved.