Speaker
Samuel Harris, Nothern Arizona University
Abstract
Synchronous games that are equivalent, in some sense, preserve certain properties about winning strategies. In this talk, we will see how one can transform any synchronous game into a graph homomorphism game. More specifically, we’ll see that every synchronous game is equivalent, in some weak sense, to a three-coloring game for an associated undirected graph, and we’ll give an upper bound on the number of vertices required for the graph. As a result, we will obtain a quantum version of Lovasz’s reduction theorem of the k-coloring problem of a graph to the 3-coloring problem of a graph that holds in all quantum models, extending and simplifying the work of Z. Ji in the finite-dimensional model. This work uses a weak *-equivalence of games that we will describe.