Sum-of-Squares method and approximation algorithms

Cargèse workshop on combinatorial optimization. pdf

abstract

Survey talk on recent applications of the sum-of-squares method for NP-hard approximation algorithms.

keywords

sum-of-squares method, semidefinite programming, approximation algorithms.