Candidate hard unique game
From MaRDI portal
Publication:5361819
DOI10.1145/2897518.2897531zbMath1373.68240MaRDI QIDQ5361819
Subhash A. Khot, Dana Moshkovitz
Publication date: 29 September 2017
Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2897518.2897531
semidefinite programming; direct product; Lasserre hierarchy; integrality gap; unique games conjecture; two-prover games; real code; approximate real linear equations
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Computational topology and the Unique Games Conjecture, Noise stability and correlation with half spaces