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.