MIPco=coRE and generalized compression framework
Junqiao Lin | Centrum Wiskunde & Informatica (CWI)
Nonlocal games is a mathematical model used to model entanglement. Recently, Ji et al shows that estimating the optimal success rate for a nonlcoal game under the quantum (tensor) model is uncomputable in the celebrated result MIP*=RE result. A key part of this breakthrough involves a compression theorem for nonlocal games, a way to shrink the question and answer size of the game while preserving the optimal success rate to some degree.
In this talk, I will introduce the generalized compression framework, a generalization of the compression argument used in the MIP*=RE theorem, which could be applied to other computation problems unrelated to nonlocal games. I will explore how this framework can be used to prove the coRE-completeness of the complexity class MIPco, an MIP protocol where provers are allowed access to the commuting operator model of entanglement.
This talk is based on the upcoming paper MIPco=coRE.
Location
-
QNC 1201
-
-
Meeting ID: 992 2420 0124
-
Passcode: 983537
-