Computer Science/Discrete Mathematics Seminar I

In this talk, I'll describe connections between the unique games conjecture (or more precisely, the closely relatedly problem of small-set expansion) and the quantum separability problem. Remarkably, not only are the problems related, but the leading candidate algorithms turn out to be essentially equivalent: for unique games, the algorithm is called the Lasserre hierarchy, and for quantum separability, it is called the "k-extendable" relaxation. As a result, insights from quantum information theory may provide an unexpected route to either quasipolynomial algorithms or hardness results for unique games. I will describe conjectures in quantum information theory that would imply nontrivial results in unique games, and give my perspective on what I see as promising directions. The talk will not assume any knowledge of quantum mechanics, or for that matter, of the unique games conjecture or the Lasserre hierarchy. It is partly based on 1205.4484 and 1210.6367.