From Nonlocal Games to Undecidability

In this lecture I will present basic elements of the theory of nonlocal games from quantum information theory and give some examples. I will then introduce the idea of "compressing" the complexity of nonlocal games, and show how the right form of compression leads to undecidability of a natural optimization problem associated with the games. Using the results from the first lecture, the undecidability result will imply a negative answer to Tsirelson's problem and its equivalent problems in operator algebras.