Lower Bounds for CSP Refutation by SDP Hierarchies.
Ryuhei MoriDavid WitmerPublished in: APPROX-RANDOM (2016)
Keyphrases
- lower bound
- constraint satisfaction problems
- random instances
- upper bound
- np hard
- semidefinite programming
- branch and bound
- semi definite programming
- inductive inference
- tree decomposition
- branch and bound algorithm
- theorem prover
- decomposition methods
- vc dimension
- linear programming
- arc consistency
- theorem proving
- finding optimal solutions
- np complete
- constraint satisfaction
- constraint propagation
- objective function
- optimal solution
- hierarchical structure
- constraint programming
- lower and upper bounds
- semidefinite program
- max sat
- worst case
- closest string
- constraint networks
- space complexity
- model selection
- automated theorem proving
- dynamic programming
- min sum
- convex optimization