Subsampling mathematical relaxations and average-case complexity

with Boaz Barak, Moritz Hardt, Thomas Holenstein. SODA 2011.

PDF

abstract

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

Let $\mathcal{C}$ be a family of CSPs such as 3SAT, Max-Cut, etc.., and let $\Pi$ be a mathematical program that is a relaxation for $\mathcal{C}$, in the sense that for every instance $\mathcal P\in\mathcal C$, $\Pi(\mathcal P)$ is a number in $[0,1]$ upper bounding the maximum fraction of satisfiable constraints of $\mathcal P$. Loosely speaking, we say that subsampling holds for $\mathcal C$ and $\Pi$ if for every sufficiently dense instance $\mathcal{P} \in \mathcal{C}$ and every $\varepsilon>0$, if we let $\mathcal{P}'$ be the instance obtained by restricting $\mathcal{P}$ to a sufficiently large constant number of variables, then $\Pi(\mathcal P') \in (1\pm \varepsilon)\Pi(\mathcal P)$. We say that weak subsampling holds if the above guarantee is replaced with $\Pi(\mathcal P') = 1-\Theta(\gamma)$ whenever $\Pi(\mathcal P)= 1-\gamma$, where $\Theta$ hides only absolute constants. We obtain both positive and negative results, showing that:

1. Subsampling holds for the Basic LP and Basic SDP programs. Basic SDP is a variant of the semi-definite program considered by Raghavendra (2008), who showed it gives an optimal approximation factor for every constraint-satisfaction problem under the unique games conjecture. Basic LP is the linear programming analog of Basic SDP.

2. For tighter versions of Basic SDP obtained by adding additional constraints from the Lasserre hierarchy, weak subsampling holds for CSPs of unique games type.

3. There are non-unique CSPs for which even weak subsampling fails for the above tighter semi-definite programs. Also there are unique CSPs for which (even weak) subsampling fails for the Sherali-Adams linear programming hierarchy.

As a corollary of our weak subsampling for strong semi-definite programs, we obtain a polynomial-time algorithm to certify that random geometric graphs (of the type considered by Feige and Schechtman, 2002) of max-cut value $1-\gamma$ have a cut value at most $1-\gamma/10$. More generally, our results give an approach to obtaining average-case algorithms for CSPs using semi-definite programming hierarchies.