QLunch: Pieter Spaas

Speaker: Pieter Spaas

Title: Gap-preserving reductions and RE-completeness of independent set games

Abstract: We will describe a reduction from synchronous nonlocal games to independent set games. This was first done for perfect strategies by Mančinska, Roberson, and Varvitsiotis, and we will show how to lift this result to approximate strategies. This yields a so-called gap-preserving reduction, with further implications towards complexity questions related to nonlocal games. We will introduce the necessary background, describe and motivate these results, and sketch the main ideas behind their proofs. This talk is based on joint work with Laura Mančinska and Taro Spirig.