The Generalized Compression Framework and MIPco=coRE

In this talk, I will introduce the generalized compression framework, a framework for showing uncomputability results based on “compressing” the problem size. The generalized compression framework is a refinement over the argument given in the celebrated MIP*=RE theorem, as it requires fewer assumptions and could potentially be applied to other computational problems. I will also discuss some of the differences between MIP* and its classical counterpart, MIP, and discuss why adding quantum entanglement allows the compression of the problem size. Lastly, I will explore how this framework can be applied to the complexity class MIPco, an infinite-dimensional variant of MIP*, in order to show that it is coRE-complete.

This is a “mostly” quantum-free talk.