TY - GEN
T1 - Sum of squares lower bounds for refuting any CSP
AU - Kothari, Pravesh K.
AU - Mori, Ryuhei
AU - O'Donnell, Ryan
AU - Witmer, David
N1 - Publisher Copyright:
© 2017 ACM.
PY - 2017/6/19
Y1 - 2017/6/19
N2 - Let P: {0, 1}k → {0,1} be a nontrivial k-ary predicate. Consider a random instance of the constraint satisfaction problem CSP(P) on n variables with An constraints, each being P applied to k randomly chosen literals. Provided the constraint density satisfes Δ ≥≥ 1, such an instance is unsatisfable with high probability. The refutation problem is to efficiently find a proof of unsatisfability. We show that whenever the predicate P supports a t-wise uniform probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree d = Θ(n/Δ2/(t-1)longΔ) (which runs in time nO(d)) cannot refute a random instance of CSP(P). In particular, the polynomial-time SOS algorithm requires Ω(n(t+1)/2) constraints to refute random instances of CSP(P) when P supports a t-wise uniform distribution on its satisfying assignments. Together with recent work of Lee, Raghavendra, Steurer (2015), our result also implies that any polynomial-size semidefinite programming relaxation for refutation requires at least Ω(n(t+1)/2) constraints. More generally, we consider the δ-refutation problem, in which the goal is to certify that at most a (1 - δ)-fraction of constraints can be simultaneously satisfed. We show that if P is δ-close to supporting a t-wise uniform distribution on satisfying assignments, then the degree-Ω(n/Δ2/(t-1)logΔ) SOS algorithm cannot (δ + o(1))- refute a random instance of CSP(P). This is the first result to show a distinction between the degree SOS needs to solve the refutation problem and the degree it needs to solve the harder δ-refutation problem. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate P, they give a three-way hardness tradeof between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of Allen, O'Donnell, Witmer (2015) and Raghavendra, Rao, Schramm (2016), this full three-way tradeof is tight, up to lower-order factors.
AB - Let P: {0, 1}k → {0,1} be a nontrivial k-ary predicate. Consider a random instance of the constraint satisfaction problem CSP(P) on n variables with An constraints, each being P applied to k randomly chosen literals. Provided the constraint density satisfes Δ ≥≥ 1, such an instance is unsatisfable with high probability. The refutation problem is to efficiently find a proof of unsatisfability. We show that whenever the predicate P supports a t-wise uniform probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree d = Θ(n/Δ2/(t-1)longΔ) (which runs in time nO(d)) cannot refute a random instance of CSP(P). In particular, the polynomial-time SOS algorithm requires Ω(n(t+1)/2) constraints to refute random instances of CSP(P) when P supports a t-wise uniform distribution on its satisfying assignments. Together with recent work of Lee, Raghavendra, Steurer (2015), our result also implies that any polynomial-size semidefinite programming relaxation for refutation requires at least Ω(n(t+1)/2) constraints. More generally, we consider the δ-refutation problem, in which the goal is to certify that at most a (1 - δ)-fraction of constraints can be simultaneously satisfed. We show that if P is δ-close to supporting a t-wise uniform distribution on satisfying assignments, then the degree-Ω(n/Δ2/(t-1)logΔ) SOS algorithm cannot (δ + o(1))- refute a random instance of CSP(P). This is the first result to show a distinction between the degree SOS needs to solve the refutation problem and the degree it needs to solve the harder δ-refutation problem. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate P, they give a three-way hardness tradeof between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of Allen, O'Donnell, Witmer (2015) and Raghavendra, Rao, Schramm (2016), this full three-way tradeof is tight, up to lower-order factors.
KW - Constraint satisfaction
KW - Lower bounds
KW - Sum-of-Squares semidefinite programming hierarchy
UR - http://www.scopus.com/inward/record.url?scp=85024406950&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85024406950&partnerID=8YFLogxK
U2 - 10.1145/3055399.3055485
DO - 10.1145/3055399.3055485
M3 - Conference contribution
AN - SCOPUS:85024406950
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 132
EP - 145
BT - STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
A2 - McKenzie, Pierre
A2 - King, Valerie
A2 - Hatami, Hamed
PB - Association for Computing Machinery
T2 - 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
Y2 - 19 June 2017 through 23 June 2017
ER -