Speaker
Description
Binary constraint system games are a generalization of the Mermin-Peres magic square game introduced by Cleve and Mittal. Thanks to the recent MIP=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen, BCS games can be used to construct a proof system for any language in MIP, the class of languages with a multiprover interactive proof system where the provers can share entanglement. This means that we can apply logical reductions for binary constraint systems to MIP protocols, and also raises the question: how complicated do our constraint systems have to be to describe all of MIP? In this talk, I'll give a general overview of this subject, including an application of logical reductions to showing that all languages in MIP have a perfect zero knowledge proof system (joint work with Kieran Mastel), and one obstacle to expressing all of MIP with linear constraints (joint work with Connor Paddock).
External references
- 24050012
- 3533e88c-3fa2-47ec-9107-e9c0fee69b54
