Computability and compression of nonlocal games
Sajjad Nezhadi, University of Maryland - College Park
Recently, works such as the landmark MIP*=RE paper by Ji et. al. have established deep connections between computability theory and the power of nonlocal games with entangled provers. Many of these works start by establishing compression procedures for nonlocal games, which exponentially reduce the verifier's computational task during a game. These compression procedures are then used to construct reductions from uncomputable languages to nonlocal games, by a technique known as iterated compression.
In this talk, I will introduce and contrast various versions of the compression procedure and discuss their use cases. In particular, I will demonstrate how each can be used to construct reductions from various languages in the first two levels of the arithmetical hierarchy to complexity classes defined using entangled nonlocal games. Time permitting, I will also go through a high-level overview of some ingredients involved in performing compression.
Join the seminar on Zoom!
Meeting link: https://umd.zoom.us/j/94516883349?pwd=Qnc4NFdWNzMzVU5NS0dqbW4vdy93dz09
Add event to calendar
Apple Google Office 365 Outlook Outlook.com Yahoo
This virtual seminar is jointly sponsored by the Institute for Quantum Computing and the Joint Center for Quantum Information and Computer Science.
If you are interested in presenting at a future seminar, please email either Daniel Grier (daniel.grier@uwaterloo.ca) or Hakop Pashayan (hpashaya@uwaterloo.ca).