We present a new efficient sampling method for approximating
r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on
n variables up to an additive error \epsilon n^r.We prove a new
general paradigm in that it suffices, for a given set of constraints,
to pick a small uniformly random subset of its variables, and the optimum
value of the subsystem induced on these variables gives (after a direct
normalization) an approximation to the optimum of the whole system up to
an additive error of \epsilon n^r. Our method gives for the first time a
polynomial in \epsilon^-1 bound on the sample size necessary to carry out
the above approximation. Moreover, this bound is independent in the
exponent on the dimension r. The above method gives a completely uniform
sampling technique for all the MAX-rCSP problems, and improves the best
known sample bounds for the low dimensional problems,like MAX-CUT.

The method of solution depends on a new result on the cut norm of random
subarrays, and a new sampling technique for high dimensional linear programs.
This method could be also of independent interest.