Abstract
In the model of one-round two-prover interactive games, two incommunicated players that share a coordinated strategy answer a pair of randomly chosen queries issued by a verifier. On receiving the answers, the verifier decides to accept or reject according to a publicly known predicate. The goal of the players is to maximize the probability that the verifier accepts. This model has been used in several areas of theoretical computer science, combinatorics, and (quantum) information theory, as an abstraction for a variety of computational or experimental processes. In this talk I will survey some new results on the classification problem of such games that were obtained from the recent realization that the model of two-prover interactive games can be analyzed through the theory of locally consistent instances of an associated constraint satisfaction problem. These results are obtained from pulling a thread that stitches all four areas of the program together: probability theory through the multivariate moment problem, database theory through the structure of solution-spaces for join queries, quantum information theory through the problems of locality and contextuality, and finite and algorithmic model theory through the method of Ehrenfeucht-Fraisse games.