On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction.
Boaz BarakGuy KindlerDavid SteurerPublished in: ITCS (2013)
Keyphrases
- constraint satisfaction
- semidefinite
- average case
- semidefinite programming
- constraint satisfaction problems
- convex relaxation
- worst case
- uniform distribution
- sufficient conditions
- higher dimensional
- interior point methods
- convex sets
- heuristic search
- finite dimensional
- multiple kernel learning
- maximum margin
- support vector
- linear programming
- lower bound