The long code is a central tool in hardness of approximation, especially inquestions related to the unique games conjecture. We construct a new code thatis 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 0">0, we show the existence of an n vertex graph G where everyset of o(n) vertices has expansion 1−, but G’s adjacency matrix has morethan exp(logn) eigenvalues larger than 1−, where  depends only on . 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 moduloK into instances with alphabet k with a blowup of Kpolylog(K), improving overthe previously known gadget with blowup of 2K.

3. An n variable integrality gap for Unique Games that that survives exp(poly(loglogn)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(loglogn).

We show a connection between the local testability of linear codes and small setexpansion in certain related Cayley graphs, and use this connection to derandomizethe noise graph on the Boolean hypercube.