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