ECCC-Report TR13-114https://eccc.weizmann.ac.il/report/2013/114Comments and Revisions published for TR13-114en-usFri, 11 Oct 2013 23:38:29 +0300
Revision 1
| Locally Testable Codes and Cayley Graphs |
Yuan Zhou,
Parikshit Gopalan,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2013/114#revision1We 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}
Fri, 11 Oct 2013 23:38:29 +0300https://eccc.weizmann.ac.il/report/2013/114#revision1
Paper TR13-114
| Locally Testable Codes and Cayley Graphs |
Yuan Zhou,
Parikshit Gopalan,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2013/114We 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}
Tue, 27 Aug 2013 04:10:14 +0300https://eccc.weizmann.ac.il/report/2013/114