A quantum unique games conjecture

DOI10.4230/LIPICS.ITCS.2025.76MaRDI QIDQ7296723zbMATH OpenFDO

Authors Hamoon Mousavi, Taro Spirig

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2025.76

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A synchronous game for binary constraint systems
• About the Connes embedding conjecture
• Characterization of binary constraint system games
• Connes' embedding problem and Tsirelson's problem
• Estimating quantum chromatic numbers
• Gadgets, Approximation, and Linear Programming
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 1263221 (Why is no real title available?)
• scientific article; zbMATH DE number 1306875 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Interactive proofs and the hardness of approximating cliques
• MIP* = RE
• Non-deterministic exponential time has two-prover interactive protocols
• Nonlocal games, compression theorems, and the arithmetical hierarchy
• On the optimality of the random hyperplane rounding technique for MAX CUT
• On the power of multi-prover interactive protocols
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Proposed experiment to test local hidden-variable theories
• Quantum analogues of the Bell inequalities. The case of two spatially separated domains
• Some optimal inapproximability results
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The PCP theorem by gap amplification
• The set of quantum correlations is not closed
• The theory of quantum information
• Tsirelson's problem and an embedding theorem for groups arising from non-local games
• Tsirelson's problem and Kirchberg's conjecture
• Two-Prover Protocols---Low Error at Affordable Rates
• Unique games hardness of quantum max-cut, and a conjectured vector-valued Borell's inequality
• Unique games with entangled provers are easy
• Universality of graph homomorphism games and the quantum coloring problem

This page was built for publication: A quantum unique games conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296723)