We initiate a study of when the value of mathematical relaxations such aslinear and semi-definite programs for constraint satisfaction problems (CSPs)is approximately preserved when restricting the instance to a sub-instanceinduced by a small random subsample of the variables.

Let be a family of CSPs such as 3SAT, Max-Cut, etc., and let be a mathematical program that is a \emph{relaxation} for ,in the sense that for every instance , () is a number in[01] upper bounding the maximum fraction of satisfiable constraints of. Loosely speaking, we say that \emph{subsampling holds} for and if for every sufficiently dense instance and every 0">0, if we let be the instance obtained byrestricting to a sufficiently large constant number ofvariables, then ()(1)(). We say that \emph{weaksubsampling} holds if the above guarantee is replaced with ()=1−() whenever ()=1− , where hides onlyabsolute constants. We obtain both positive and negative results, showingthat:

\begin{enumerate}

\item Subsampling holds for the BasicLP and BasicSDP programs. BasicSDP isa variant of the semi-definite program considered by Raghavendra (2008), whoshowed it gives an optimal approximation factor for everyconstraint-satisfaction problem under the unique games conjecture. BasicLP isthe linear programming analog of BasicSDP.

\item For tighter versions of BasicSDP obtained by adding additionalconstraints from the Lasserre hierarchy, \emph{weak} subsampling holds forCSPs of unique games type.

\item There are non-unique CSPs for which even weak subsampling fails for theabove tighter semi-definite programs. Also there are unique CSPs for which(even weak) subsampling fails for the Sherali-Adams \emph{linear programming}hierarchy.

\end{enumerate}

As a corollary of our weak subsampling for strong semi-definite programs, weobtain a polynomial-time algorithm to certify that \emph{random geometricgraphs} (of the type considered by Feige and Schechtman, 2002) of max-cutvalue 1− have a cut value at most 1−10 . More generally, ourresults give an approach to obtaining average-case algorithms for CSPs usingsemi-definite programming hierarchies.