Subsampling Mathematical Relaxations and Average-case Complexity

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

Abstract

We initiate a study of when the value of mathematical relaxations such as linear and semidefinite 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. We show that subsampling holds for BasicLP and BasicSDP programs. For tighter versions obtained by adding constraints from the Lasserre hierarchy, weak subsampling holds for CSPs of unique games type, while it fails for non-unique CSPs. Additionally, we find that subsampling fails for the Sherali-Adams linear programming hierarchy even on unique CSPs. As a corollary, we obtain a polynomial-time algorithm to certify that random geometric graphs of max-cut value $1-\gamma$ have a cut value at most $1-\gamma/10$.

Introduction

Constraint Satisfaction Problems (CSPs), such as 3SAT and Max-Cut, are fundamental to computer science. While finding exact solutions is typically NP-hard, researchers utilize mathematical relaxations—specifically Linear Programming (LP) and Semidefinite Programming (SDP)—to compute polynomial-time upper bounds on the maximum fraction of satisfiable constraints.

A critical question for efficiency and property testing is whether the value of these relaxations is preserved when the problem instance is restricted to a small, random subsample of variables. While prior work established that the actual objective value (the true maximum satisfiability) is often preserved under subsampling, this paper investigates whether the algorithmic proxy—the relaxation value—shares this robustness.

The Subsampling Property

We say that subsampling holds for a CSP family $C$ and a relaxation $\Pi$ if, for a sufficiently dense instance $P \in C$, a sub-instance $P'$ induced by a constant number of random variables satisfies $\Pi(P') \approx \Pi(P)$. "Weak subsampling" refers to a looser guarantee where $\Pi(P') = 1 - \Theta(\gamma)$ whenever $\Pi(P) = 1 - \gamma$.

Analysis of Mathematical Relaxations

The authors analyze a hierarchy of relaxations, ranging from basic programs to powerful hierarchies like Sherali-Adams and Lasserre (Sum-of-Squares).

Relationships and subsampling properties of various mathematical relaxations.

As illustrated in the figure above, the "Basic" versions of LP and SDP are remarkably robust to subsampling. However, as the relaxations become more complex, their behavior diverges. The Sherali-Adams LP hierarchy fails to preserve value even for Unique Games. In contrast, the Lasserre SDP hierarchy exhibits weak subsampling for Unique Games but fails for non-unique CSPs. In non-unique cases, the hierarchy can detect global contradictions in large instances that disappear in small samples, causing the relaxation value to fluctuate significantly.

Key Insights and Results

  1. Robustness of Basic Relaxations: BasicLP and BasicSDP values are preserved within $(1 \pm \epsilon)$ on samples of size $O(n/\Delta)$. This is proven using dimension reduction and discretization, viewing BasicSDP as a CSP over a constant-sized alphabet.
  2. The Unique Games Advantage: For the Lasserre hierarchy, the authors introduced a "proxy graph" method. For Unique Games, a subsample of a "third power" of the graph can decode a solution for the original instance, ensuring the relaxation value remains stable.
  3. Max-Cut in Random Geometric Graphs: A significant application of this theory is a new polynomial-time algorithm for certifying Max-Cut values in random geometric graphs ($G_{n,d,\gamma}$). By treating these graphs as random subsamples of a continuous "sphere graph," the authors transferred continuous mathematical results to the discrete algorithmic domain. They can now certify a cut value of at most $1-\gamma/10$ when the true value is $1-\Omega(\sqrt{\gamma})$.

Conclusion

This work highlights a fundamental gap between the power of LP and SDP hierarchies regarding subsampling. While basic relaxations are stable, the Lasserre hierarchy's success is tied to the "uniqueness" of the underlying CSP. Future research may explore whether "strong" subsampling (arbitrary accuracy) is possible for the Lasserre hierarchy on Unique Games and seek to generalize these average-case algorithms to other distributions beyond geometric graphs.

Summary updated

Abstract

We initiate a study of when the value of mathematical relaxations such as linear and semidefinite 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 $C$ be a family of CSPs such as 3SAT, Max-Cut, etc., and let $Π$ be a relaxation for $C$, in the sense that for every instance $P\in C$, $Π(P)$ is an upper bound the maximum fraction of satisfiable constraints of $P$. Loosely speaking, we say that subsampling holds for $C$ and $Π$ if for every sufficiently dense instance $P \in C$ and every $ε>0$, if we let $P'$ be the instance obtained by restricting $P$ to a sufficiently large constant number of variables, then $Π(P') \in (1\pm ε)Π(P)$. We say that weak subsampling holds if the above guarantee is replaced with $Π(P')=1-Θ(γ)$ whenever $Π(P)=1-γ$. We show: 1. Subsampling holds for the BasicLP and BasicSDP programs. BasicSDP is a variant of the relaxation considered by Raghavendra (2008), who showed it gives an optimal approximation factor for every CSP under the unique games conjecture. BasicLP is the linear programming analog of BasicSDP. 2. For tighter versions of BasicSDP 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 semidefinite programs. Also there are unique CSPs for which subsampling fails for the Sherali-Adams linear programming hierarchy. As a corollary of our weak subsampling for strong semidefinite 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-γ$ have a cut value at most $1-γ/10$.
BibTeX
@inproceedings{barak2011subsampling,
  author = {Boaz Barak and Moritz Hardt and Thomas Holenstein and David Steurer},
  title = {{Subsampling Mathematical Relaxations and Average-case Complexity}},
  booktitle = {SODA},
  year = {2011},
  doi = {10.1137/1.9781611973082.41},
}
Figure