Subsampling Mathematical Relaxations and Average-case Complexity
Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer · 2010
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 C be a family of CSPs such as 3SAT, Max-Cut, etc.., and let Π be a mathematical program that is a relaxation for C, in the sense that for every instance P ∈ C, Π(P) is a number in [0, 1] upper bounding 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 ∈ 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′) ∈ (1±ε)Π(P). We say that weak subsampling holds if the above guarantee is replaced with Π(P′) = 1−Θ(γ) whenever Π(P) = 1 − γ, where Θ hides only absolute constants. We obtain both positive and negative results, showing that: 1. 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.