Name
Abstract | ||
|---|---|---|
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.
|
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2897518.2897531 | STOC '16: Symposium on Theory of Computing
Cambridge
MA
USA
June, 2016 |
Keywords | Field | DocType |
Unique Games Conjecture (UGC),Probabilistically Checkable Proofs (PCP),two prover games,real code,half-space,Gaussian isoperimetry,direct product theorem,leakage,approximate real linear equations,semidefinite programming (SDP),Lasserre hierarchy,integrality gap | Discrete mathematics,Combinatorics,System of linear equations,Unique games conjecture,Computer science,Gaussian,Soundness,Completeness (statistics),Hadamard code,Semidefinite programming,Encoding (memory) | Conference |
ISSN | ISBN | Citations |
0737-8017 | 978-1-4503-4132-5 | 6 |
PageRank | References | Authors |
0.53 | 29 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Subhash Khot | 1 | 2064 | 112.51 |
| Dana Moshkovitz | 2 | 368 | 19.14 |