Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique.
Raghu MekaAvi WigdersonPublished in: Electron. Colloquium Comput. Complex. (2013)
Keyphrases
- lower bound
- upper bound
- branch and bound algorithm
- lower bounding
- branch and bound
- vc dimension
- worst case
- objective function
- average case complexity
- lower and upper bounds
- maximum clique
- special case
- low order
- quadratic assignment problem
- query processing
- set of randomly generated instances
- constant factor approximation algorithm