Candidate hard unique game

We propose a candidate reduction for ruling out polynomial-time algorithms for unique games, either under plausible complexity assumptions, or unconditionally for Lasserre semi-definite programs with a constant number of rounds. We analyze the completeness and Lasserre solution of our construction, and provide a soundness analysis in a certain setting of interest. Addressing general settings is tightly connected to a question on Gaussian isoperimetry. Our construction is based on our previous work on the complexity of approximately solving a system of linear equations over reals, which we suggested as an avenue towards a (positive) resolution of the Unique Games Conjecture. The construction employs a new encoding scheme that we call the real code. The real code has two useful properties: like the long code, it has a unique local test, and like the Hadamard code, it has the so-called sub-code covering property.

Authors

• Subhash Khot
• Dana Moshkovitz

Keywords

No keywords are indexed for this paper.