Making the long code shorter

with Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra. FOCS 2012.


Invited to FOCS 2012 special issue


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 effcient, 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\varepsilon > 0, we show the existence of an nn vertex graph GG where every set of o(n)o(n) vertices has expansion 1ε1 - \varepsilon, but GG's adjacency matrix has more than exp(logδn)\exp(\log^\delta n) eigenvalues larger than 1ε1 - \varepsilon, where δ\delta depends only on ε\varepsilon. 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(logn)\mathrm{poly}(\log n) such eigenvalues.
  2. A gadget that reduces unique games instances with linear constraints modulo KK into instances with alphabet kk with a blowup of Kpolylog(K)K^{\mathrm{polylog}(K)}, improving over the previously known gadget with blowup of 2K2^K.
  3. An nn variable integrality gap for Unique Games that that survives exp(poly(loglogn))\exp(\mathrm{poly}(\log \log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(loglogn)\mathrm{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.


  • small-set expansion
  • lower bounds
  • Unique Games Conjecture
  • eigenvalues
  • strong relaxations