The goal of this Dagstuhl Seminar is to bring together two research communities that have been studying closely related problems through vastly different formalisms and methodologies.

The first community studies nonlocal games, a framework originating in quantum physics. A nonlocal game is a mathematical abstraction of experiments designed to reveal the incompatibility of quantum mechanics with classical local-realistic theories. In the 1960s, Bell and Kochen–Specker proved the existence of games where classical players can be outperformed by quantum players, who may share an entangled state and base their answers on local measurements of their respective subsystems. This game-theoretic framework for capturing non-classical phenomena in quantum theory has later evolved into a fully-fledged quantum version of graph theory, which seeks to lift graph invariants to their quantum counterparts defined in terms of quantum strategies in nonlocal games.

The second community develops the algebraic approach to constraint satisfaction problems. This is a central strand of computational complexity theory, whose long-term goal is to determine, for increasingly broad classes of computational problems involving the satisfiability of local constraints, whether efficient algorithms exist or whether the problems are inherently intractable. From the Cook–Levin theorem on the NP-completeness of SAT and Karp's seminal list of NP-complete problems, through Schaefer's and Hell–Nešetřil's dichotomy theorems for Boolean and graph CSPs, to Bulatov's and Zhuk's independent proofs of the Feder–Vardi CSP Dichotomy Conjecture, this line of research has progressively evolved into a surprisingly rich structural theory of complexity based on a broad range of mathematical tools, with the language of Turing machines and algorithms gradually giving way to that of universal algebra, logic, and category theory.

Recent years have witnessed a growing body of work indicating that techniques traditionally used to analyse the power of quantum players in nonlocal games, largely rooted in operator algebra, can be fruitfully integrated with methods from algebraic CSP theory. In particular, the latter framework appears to provide powerful tools to investigate when quantum entanglement pushes decision problems beyond computability, thus refining the MIP*=RE theorem with finer-grained, predicate-dependent classifications. Despite this compelling evidence of convergence, the distinct backgrounds of the two communities have so far limited systematic interaction between their research groups, which remain largely separate. This seminar aims to catalyse contact between the two communities and turn this emerging convergence into a shared research programme.

Creative Commons BY 4.0

Samson Abramsky, Lorenzo Ciardo, Antoine Mottet, and David Earl Roberson