Abstract
Monogamy relations and de Finetti theorems have broad application, including to quantum key distribution, Hamiltonian complexity, analyzing non-local games and even classical optimization algorithms. One limitation of most work in this space is that the number of systems needs to grow like a power of the dimension of each system. Brandao, Christandl and Yard achieved a major breakthrough by making use of information theory to reduce the number of systems needed to scale only like the logarithm of the local dimension. I will describe a further improvement of their theorem which has a simpler proof and generalizes to multipartite states and non-signaling distributions. Next I'll describe several applications to non-local games, quantum complexity theory, and other topics. Finally, I'll explain how conjectured improvements of these results could resolve several major open problems in classical and quantum complexity theory.