  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 eps > 0, we show the existence of an n vertex graph G where every
set of o(n) vertices has expansion 1 - eps, but G's adjacency matrix has more
than exp(log^delta n) eigenvalues larger than 1 - eps, where delta depends only
on eps. 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.
