Revision #1 Authors: Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

Accepted on: 29th April 2010 22:45

Downloads: 4765

Keywords:

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 \emph{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 \emph{subsampling holds} for $\mathcal{C}$ and

$\Pi$ if for every sufficiently dense instance $\mathcal{P} \in \mathcal{C}$

and every $\epsilon>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 \epsilon)\Pi(\mathcal{P})$. We say that \emph{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:

\begin{enumerate}

\item Subsampling holds for the BasicLP and BasicSDP programs. BasicSDP 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. BasicLP is

the linear programming analog of BasicSDP.

\item For tighter versions of BasicSDP obtained by adding additional

constraints from the Lasserre hierarchy, \emph{weak} subsampling holds for

CSPs of unique games type.

\item 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 \emph{linear programming}

hierarchy.

\end{enumerate}

As a corollary of our weak subsampling for strong semi-definite programs, we

obtain a polynomial-time algorithm to certify that \emph{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.

Several more general results that subsume the previous paper.

TR09-129 Authors: Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

Publication: 30th November 2009 05:50

Downloads: 4197

Keywords:

We study the question of whether the value of mathematical programs such as

linear and semidefinite programming hierarchies on a graph $G$, is preserved

when taking a small random subgraph $G'$ of $G$. We show that the value of the

Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is

approximately equal to the SDP value of $G$. Moreover, this holds even if the

SDP is augmented with any constraint from a large natural family $\mathcal{C}$

of constraints that includes all constraints from the hierarchy of Lasserre

(2001). The subgraph $G'$ is up to a constant factor as small as possible.

In contrast, we show that for linear programs this is \emph{not} the case, and

there are graphs $G$ that have small value for the \maxcut LP with triangle

inequalities, but for which a random subgraph $G'$ has value $1-o(1)$ even for

the LP augmented with $n^{\epsilon}$ rounds of the Sherali-Adams hierarchy.

Our results yield a general approach to use the Lasserre hierarchy to solve

\maxcut on the average on certain types of input distributions. In particular

we show that a natural candidate for hard instances of \maxcut--- the

Feige-Schechtman (2002) graphs that are obtained by sampling a random subset

$S$ of the sphere and placing an edge between pairs of points in $S$ that are

almost antipodal--- is actually easy to solve by SDPs with triangle

inequalities. Such a result can be considered more or less folklore in the

\emph{dense} case, where $S$ is large enough to form a close approximation

of the sphere, but requires quite different techniques to demonstrate in

the sparse case.