Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-142 | 1st November 2014 21:31

Candidate Lasserre Integrality Gap For Unique Games

RSS-Feed




TR14-142
Authors: Subhash Khot, Dana Moshkovitz
Publication: 2nd November 2014 01:04
Downloads: 1514
Keywords: 


Abstract:

We propose a candidate Lasserre integrality gap construction for the Unique Games problem.
Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution of the Unique Games Conjecture.
We use 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.

This write-up represents a part of a work in progress.



ISSN 1433-8092 | Imprint