Candidate hard unique game

DOI10.1145/2897518.2897531MaRDI QIDQ5361819zbMATH OpenOpenAlexFDO

Authors Subhash 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

approximate real linear equationsdirect productintegrality gapLasserre hierarchyreal codesemidefinite programmingtwo-prover gamesunique games conjecture

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)

Recommendations

• Near-optimal algorithms for unique games
• Approximation algorithms for unique games
• A note on unique games
• A new point of NP-hardness for unique games
• Making the Long Code Shorter

Cited in

(9)

• Noise stability and correlation with half spaces
• Unlikely Candidate—Unexpected Entry [Historical Perspectives]
• Computational topology and the unique games conjecture
• Three candidate plurality is stablest for small correlations
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Towards a proof of the 2-to-1 games conjecture
• Almost consistent systems of linear equations
• Sphere valued noise stability and quantum max-cut hardness
• Parameterized approximability for modular linear equations

This page was built for publication: Candidate hard unique game

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