Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-142 | 3rd August 2015 18:00

Making the long code shorter

RSS-Feed

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 ecient, 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 $\epsilon > 0$, we show the existence of an $n$ vertex graph G where every
set of $o(n)$ vertices has expansion $1 - \epsilon$, but G’s adjacency matrix has more
than $exp(log^{\delta} n)$ eigenvalues larger than $1 - \epsilon$, where $\delta$ depends only on $\epsilon$. 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 $K^{polylog(K)}$, improving over
the previously known gadget with blowup of $2^K$.

3. An n variable integrality gap for Unique Games that 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.



Changes to previous version:

Final journal version.


Paper:

TR11-142 | 2nd November 2011 07:31

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





TR11-142
Authors: Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Publication: 2nd November 2011 07:36
Downloads: 3759
Keywords: 


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 ecient, 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 $\epsilon > 0$, we show the existence of an $n$ vertex graph G where every
set of $o(n)$ vertices has expansion $1 - \epsilon$, but G’s adjacency matrix has more
than $exp(log^{\delta} n)$ eigenvalues larger than $1 - \epsilon$, where $\delta$ depends only on $\epsilon$. 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 $K^{polylog(K)}$, improving over
the previously known gadget with blowup of $2^K$.

3. An n variable integrality gap for Unique Games that 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.



ISSN 1433-8092 | Imprint