



02079nas a2200133   4500008004100000245007300041210006900114260001400183520164800197100002001845700002701865700001601892856003701908       2021                        eng d00aNonlocal Games, Compression Theorems, and the Arithmetical Hierarchy0 aNonlocal Games Compression Theorems and the Arithmetical Hierarc  c10/9/20213 a<p>We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy, a classification of languages according to the complexity of arithmetical formulas defining them. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that deciding whether the (finite-dimensional) quantum value of a nonlocal game is 1 or at most 12 is complete for the class Σ1 (i.e., RE). A result of Slofstra implies that deciding whether the commuting operator value of a nonlocal game is equal to 1 is complete for the class Π1 (i.e., coRE). We prove that deciding whether the quantum value of a two-player nonlocal game is exactly equal to 1 is complete for Π2; this class is in the second level of the arithmetical hierarchy and corresponds to formulas of the form &quot;&forall;x&exist;yϕ(x,y)&quot;. This shows that exactly computing the quantum value is strictly harder than approximating it, and also strictly harder than computing the commuting operator value (either exactly or approximately). We explain how results about the complexity of nonlocal games all follow in a unified manner from a technique known as compression. At the core of our Π2-completeness result is a new &quot;gapless&quot; compression theorem that holds for both quantum and commuting operator strategies. Our compression theorem yields as a byproduct an alternative proof of Slofstra&#39;s result that the set of quantum correlations is not closed. We also show how a &quot;gap-preserving&quot; compression theorem for commuting operator strategies would imply that approximating the commuting operator value is complete for Π1.</p>1 aMousavi, Hamoon1 aNezhadi, Seyed, Sajjad1 aYuen, Henry  uhttps://arxiv.org/abs/2110.0465101278nas a2200133   4500008004100000245005800041210005700099260001500156520087600171100001501047700001701062700001601079856004901095       2017                        eng d00aRaz-McKenzie simulation with the inner product gadget0 aRazMcKenzie simulation with the inner product gadget  c2017/01/283 a<p>In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions f composed with the Inner Product gadget 1ip(x, y) = P i xiyi mod 2 of logarithmic size. In other words, given a function f : {0, 1} n &rarr; {0, 1} with deterministic query complexity D(f), we show that the deterministic communication complexity of the composed function f ◦ 1 n ip is Θ(D(f) log n), where f ◦ 1 n ip(x, y) = f(1ip(x 1 , y 1 ), . . . , 1ip(x n , y n )) where x = (x 1 , . . . , x n ), y = (y 1 , . . . , y n ) and each x i and y i are O(log n) bit strings. In [RM97] and [GPW15], the simulation algorithm is implemented for functions composed with the Indexing gadget, where the size of the gadget is polynomial in the input length of the outer function f.</p>1 aWu, Xiaodi1 aYao, Penghui1 aYuen, Henry  uhttps://eccc.weizmann.ac.il/report/2017/010/