The Unique Games Conjecture and Polynomial Optimization

Isaac Newton Institute.

abstract

We survey recent developments about the Unique Games Conjecture and sum-of-squares methods, in particular, connections to polynomial optimization, proof complexity, and quantum information theory.

This talk aims at an audience with a general optimization background.