Tutte Colloquium - William Slofstra

Title: Positivity and sums of squares in products of free algebras

Abstract: A noncommutative polynomial is said to be positive relative to some constraints if plugging matrices (or more generally, operators on a Hilbert space) satisfying the constraints into the polynomial always yields a positive operator. It is a natural problem to determine whether or not a given polynomial is positive, and if it is, to find some certificate of positivity. This problem is closely connected with noncommutative polynomial optimization, where we want to find matrices or operators that maximize the operator norm of some polynomial, subject to the constraint that some other polynomials in the operators are positive or vanish. When the algebra cut out by the constraints is a free algebra, free group algebra, or similar algebra, it's well-known that a polynomial is positive on operators satisfying the constraints if and only if it's a sum of Hermitian squares in the algebra.

In the study of nonlocal games in quantum information, we are interested in determining when a polynomial in 2n variables is positive, subject to the constraints that the first n variables commute with the second n variables (or in other words, when the constraints cut out a product of free group algebras). The recent and remarkable MIP*=RE result of Ji, Natarajan, Vidick, Wright, and Yuen shows that it is undecidable to determine whether a polynomial is positive on matrices, subject to these constraints. In this talk, I'll give an overview of the MIP*=RE result from the perspective of noncommutative polynomial optimization, and then discuss further directions opened up by this result, including recent work with Arthur Mehta and Yuming Zhao showing that it is undecidable to determine whether a polynomial in a product of group algebras is positive. In particular, this latter result shows that there are no certificates of positivity in such algebras.