Select All
PIRSA:24050012

Binary constraint systems and MIP*

APA

Slofstra, W. (2024). Binary constraint systems and MIP*. Perimeter Institute for Theoretical Physics. https://pirsa.org/24050012

William Slofstra University of Waterloo

Talk numberPIRSA:24050012
Talk Type Conference
Subject

Abstract

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).