In a maximum-r-constraint satisfaction problem with variables fx 1 ; x 2 ; y; x n g; we are given Boolean functions f 1 ; f 2 ; y; 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 qAOΓ°logΓ°1=eΓ=e 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 eq 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=e 5 Γ variables, can find an approximation to the answer to the whole problem within additive error en 2 : For rX3; 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=e: Their algorithm has a sample complexity q of OΓ°1=e 7 Γ: They (as also the earlier papers) however do not directly prove any relation between the answer to the