Name
Abstract | ||
|---|---|---|
We consider the complexity of LS+ refutations of unsatisfiable instances of Constraint Satisfaction Problems (k-CSPs) when the underlying predicate supports a pairwise independent distribution on its satisfying assignments. This is the most general condition on the predicates under which the corresponding MAX k-CSP problem is known to be approximation resistant. We show that for random instances of such k-CSPs on n variables, even after Omega(n) rounds of the LS+ hierarchy, the integrality gap remains equal to the approximation ratio achieved by a random assignment. In particular, this also shows that LS+ refutations for such instances require rank Omega(n). We also show the stronger result that refutations for such instances in the static LS+ proof system requires size exp(Omega(n)). |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/CCC.2013.21 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
matrix decomposition,theorem proving,polynomials,constraint satisfaction problems,random assignment,resistance,computational complexity | Discrete mathematics,Combinatorics,Automated theorem proving,Random assignment,Constraint satisfaction problem,Pairwise independence,Predicate (grammar),Hierarchy,Mathematics,Computational complexity theory | Conference |
Volume | ISSN | Citations |
19 | 1093-0159 | 4 |
PageRank | References | Authors |
0.43 | 12 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Madhur Tulsiani | 1 | 358 | 24.60 |
| Pratik Worah | 2 | 51 | 8.90 |