Sum of squares lower bounds for refuting any CSP.
Pravesh K. KothariRyuhei MoriRyan O'DonnellDavid WitmerPublished in: STOC (2017)
Keyphrases
- lower bound
- constraint satisfaction problems
- random instances
- upper bound
- np hard
- branch and bound
- constraint satisfaction
- finding optimal solutions
- tree decomposition
- decomposition methods
- worst case
- constraint programming
- arc consistency
- lower and upper bounds
- branch and bound algorithm
- constraint propagation
- optimal solution
- upper and lower bounds
- objective function
- quadratic assignment problem
- optimal cost
- tree decompositions
- randomly generated problems
- lower bounding
- constraint graph
- closest string
- hypertree decomposition
- solving constraint satisfaction problems
- np complete
- randomized algorithm
- constraint networks
- scheduling problem
- theoretical analysis
- polynomial approximation
- linear programming relaxation
- sample complexity