Gap-preserving compression for commuting-operator strategies

About 5 years old · traced to

Let G=(Gn)n∈N\mathscr{G}=(G_n)_{n\in\mathbb{N}} be a sequence of nonlocal games, and let the complexity of a sequence refer to the complexity of its nnth game. Gap-preserving compression conjecture. There exists a computable map GappedCompressco\texttt{GappedCompress}_{co} that, given G\mathscr{G}, outputs a sequence G′=(Gn′)n∈N\mathscr{G}'=(G_n')_{n\in\mathbb{N}} of complexity O(log⁡n)O(\log n) such that, whenever the complexity of G\mathscr{G} is at most poly(n)\mathrm{poly}(n), for every n∈Nn\in\mathbb{N},

ωco(Gn)=1⟹ωco(Gn′)=1,\omega_{co}(G_n)=1\Longrightarrow\omega_{co}(G_n')=1,

and

ωco(Gn)≤12⟹ωco(Gn′)≤12.\omega_{co}(G_n)\leq\frac{1}{2}\Longrightarrow\omega_{co}(G_n')\leq\frac{1}{2}.

The conjecture would provide a gapped compression procedure for commuting-operator strategies and could establish the hardness of approximating the commuting-operator value. Its status is unknown in the source.

References

Primary source

Hamoon Mousavi, Seyed Sajjad Nezhadi and Henry Yuen, “Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy”, arXiv:2110.04651 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.