Candidate hard unique game

Subhash Khot, Dana Moshkovitz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We propose a candidate reduction for ruling out polynomialtime algorithms for unique games, either under plausible complexity assumptions, or unconditionally for Lasserre semidefinite 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 based on half-spaces 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.

Original languageEnglish (US)
Title of host publicationSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
EditorsYishay Mansour, Daniel Wichs
PublisherAssociation for Computing Machinery
Pages63-76
Number of pages14
ISBN (Electronic)9781450341325
DOIs
StatePublished - Jun 19 2016
Event48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States
Duration: Jun 19 2016Jun 21 2016

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume19-21-June-2016
ISSN (Print)0737-8017

Other

Other48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
CountryUnited States
CityCambridge
Period6/19/166/21/16

Keywords

  • Approximate real linear equations
  • Direct product theorem
  • Gaussian isoperimetry
  • Half-space
  • Integrality gap
  • Lasserre hierarchy
  • Leakage
  • Probabilistically checkable proofs (PCP)
  • Real code
  • Semidefinite programming (SDP)
  • Two prover games
  • Unique games conjecture (UGC)

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Candidate hard unique game'. Together they form a unique fingerprint.

Cite this