TY - GEN
T1 - Candidate hard unique game
AU - Khot, Subhash
AU - Moshkovitz, Dana
PY - 2016/6/19
Y1 - 2016/6/19
N2 - 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.
AB - 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.
KW - Approximate real linear equations
KW - Direct product theorem
KW - Gaussian isoperimetry
KW - Half-space
KW - Integrality gap
KW - Lasserre hierarchy
KW - Leakage
KW - Probabilistically checkable proofs (PCP)
KW - Real code
KW - Semidefinite programming (SDP)
KW - Two prover games
KW - Unique games conjecture (UGC)
UR - http://www.scopus.com/inward/record.url?scp=84979201675&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84979201675&partnerID=8YFLogxK
U2 - 10.1145/2897518.2897531
DO - 10.1145/2897518.2897531
M3 - Conference contribution
AN - SCOPUS:84979201675
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 63
EP - 76
BT - STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Mansour, Yishay
A2 - Wichs, Daniel
PB - Association for Computing Machinery
T2 - 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
Y2 - 19 June 2016 through 21 June 2016
ER -