Candidate hard unique game

DOI10.1145/2897518.2897531zbMath1373.68240OpenAlexW2409117471MaRDI 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

zbMATH Keywords

semidefinite programmingdirect productLasserre hierarchyintegrality gapunique games conjecturetwo-prover gamesreal codeapproximate real linear equations

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Three candidate plurality is stablest for small correlations ⋮ Noise stability and correlation with half spaces ⋮ Computational topology and the Unique Games Conjecture

This page was built for publication: Candidate hard unique game