Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR09-129 | 29th April 2010 22:45

#### Subsampling Mathematical Relaxations and Average-case Complexity

Revision #1
Authors: Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer
Accepted on: 29th April 2010 22:45
Keywords:

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 \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.

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.

Changes to previous version:

Several more general results that subsume the previous paper.

### Paper:

TR09-129 | 30th November 2009 00:47

#### Subsampling Semidefinite Programs and Max-Cut on the Sphere

TR09-129
Authors: Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer
Publication: 30th November 2009 05:50
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint