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.
Topic: IQC-QuICS Math and Computer Science Seminar
Join Zoom Meeting
https://umd.zoom.us/j/94516883349?pwd=Qnc4NFdWNzMzVU5NS0dqbW4vdy93dz09
Meeting ID: 945 1688 3349
Passcode: 233641
One tap mobile
+13017158592,,94516883349# US (Washington DC)
+19294362866,,94516883349# US (New York)
Dial by your location
+1 301 715 8592 US (Washington DC)
+1 929 436 2866 US (New York)
+1 312 626 6799 US (Chicago)
+1 253 215 8782 US (Tacoma)
+1 346 248 7799 US (Houston)
+1 669 900 6833 US (San Jose)
Meeting ID: 945 1688 3349
Find your local number: https://umd.zoom.us/u/abyEXZwwR
Join by SIP
94516883349@zoomcrc.com
Join by H.323
162.255.37.11 (US West)
162.255.36.11 (US East)
115.114.131.7 (India Mumbai)
115.114.115.7 (India Hyderabad)
213.19.144.110 (Amsterdam Netherlands)
213.244.140.110 (Germany)
103.122.166.55 (Australia Sydney)
103.122.167.55 (Australia Melbourne)
149.137.40.110 (Singapore)
64.211.144.160 (Brazil)
69.174.57.160 (Canada Toronto)
65.39.152.160 (Canada Vancouver)
207.226.132.110 (Japan Tokyo)
149.137.24.110 (Japan Osaka)
Meeting ID: 945 1688 3349
Passcode: 233641