SCIENCE@home

Making the long code shorter, with applications to the Unique Games Conjecture

B. Barak,Parikshit Gopalan,J. Håstad,Raghu Meka,P. Raghavendra,David Steurer

Published 2011 in Electron. Colloquium Comput. Complex.

ABSTRACT

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: 1. For any e > 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1 − e, but G’s adjacency matrix has more than exp(log n) eigenvalues larger than 1 − e, where δ depends only on e. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2. A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of Kpolylog(K), improving over the previously known gadget with blowup of 2Ω(K). 3. An n variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube. ∗Microsoft Research New England, Cambridge MA. †Microsoft Research-Silicon Valley. ‡Royal Insitute of Technology, Stockholm, Sweden. §IAS, Princeton. Work done in part while visiting Microsoft Research, Silicon Valley. ¶Georgia Institute of Technology, Atlanta, GA. ‖Microsoft Research New England, Cambridge MA.

PUBLICATION RECORD

  • Publication year

    2011

  • Venue

    Electron. Colloquium Comput. Complex.

  • Publication date

    2011-11-02

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1111.0405
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-23 of 23 references · Page 1 of 1

CITED BY

Showing 1-26 of 26 citing papers · Page 1 of 1