Henry Yuen, University of Toronto
"Connes’ Embedding Problem through the lens of complexity theory"
The Connes Embedding Problem (CEP) is a long-standing question in the field of operator algebras, and is known to be equivalent to a number of other conjectures across mathematics. Remarkably, the CEP is also connected to fundamental questions in quantum information theory. In particular, a positive resolution to the CEP implies the existence of an algorithm to approximately compute the optimal winning probability of nonlocal games. This motivates an intriguing complexity-theoretic approach to exploring the CEP: obtaining lower bounds on the complexity of nonlocal games implies limits on the CEP, whereas upper bounds gives evidence towards its positive resolution.
I will give an overview of this fascinating connection between the Connes Embedding Problem, nonlocal games, and computational complexity, and I will discuss some new results about the complexity of nonlocal games (joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John Wright).
MC 5501