Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR13-114 | 11th October 2013 23:38

#### Locally Testable Codes and Cayley Graphs

Revision #1
Authors: Parikshit Gopalan, Salil Vadhan, Yuan Zhou
Accepted on: 11th October 2013 23:38
Keywords:

Abstract:

We give two new characterizations of (smooth, $\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$:

\begin{enumerate}
\item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a shortest-path metric that embeds into $\ell_1$ with constant distortion. This extends and gives a converse to a result of Khot and Naor (2006), which showed that codes with large dual distance imply Cayley graphs that have no low-distortion embeddings into $\ell_1$.

\item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ that has significantly more than $h$ eigenvalues near 1, which have no short linear dependencies among them and which explain'' all of the large eigenvalues. This extends and gives a converse to a recent construction of Barak et al. (2012), which showed that locally testable codes imply Cayley graphs that are small-set expanders but have many large eigenvalues.

\end{enumerate}

Changes to previous version:

The introduction and Appendix A in this revision clarifies and formalizes the relation between smooth testers (to which our results apply) and testers with bounded query complexity, correcting an error pointed out by Or Meir.

### Paper:

TR13-114 | 24th August 2013 02:18

#### Locally Testable Codes and Cayley Graphs

TR13-114
Authors: Parikshit Gopalan, Salil Vadhan, Yuan Zhou
Publication: 27th August 2013 04:10
Keywords:

Abstract:

We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$:

\begin{enumerate}
\item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a shortest-path metric that embeds into $\ell_1$ with constant distortion. This extends and gives a converse to a result of Khot and Naor (2006), which showed that codes with large dual distance imply Cayley graphs that have no low-distortion embeddings into $\ell_1$.

\item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ that has significantly more than $h$ eigenvalues near 1, which have no short linear dependencies among them and which explain'' all of the large eigenvalues. This extends and gives a converse to a recent construction of Barak et al. (2012), which showed that locally testable codes imply Cayley graphs that are small-set expanders but have many large eigenvalues.

\end{enumerate}

ISSN 1433-8092 | Imprint