### Abstract

We give two new characterizations of (F_{2} -linear, smooth) locally testable error-correcting codes in terms of Cayley graphs over F _{2}^{h}: 1. 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 l_{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 l_{1}. 2. 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.

Original language | English (US) |
---|---|

Title of host publication | ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science |

Publisher | Association for Computing Machinery, |

Pages | 76-86 |

Number of pages | 11 |

ISBN (Print) | 9781450322430 |

DOIs | |

State | Published - Jan 1 2014 |

Externally published | Yes |

Event | 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 - Princeton, NJ, United States Duration: Jan 12 2014 → Jan 14 2014 |

### Publication series

Name | ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science |
---|

### Other

Other | 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 |
---|---|

Country | United States |

City | Princeton, NJ |

Period | 1/12/14 → 1/14/14 |

### Keywords

- Cayley graphs
- Fourier analysis
- Locally testable codes
- Metric embeddings
- Spectral graph theory

### ASJC Scopus subject areas

- Computational Theory and Mathematics

### Cite this

*ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science*(pp. 76-86). (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science). Association for Computing Machinery,. https://doi.org/10.1145/2554797.2554807

**Locally testable codes and cayley graphs.** / Gopalan, Parikshit; Vadhan, Salil; Zhou, Yuan.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science.*ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science, Association for Computing Machinery, pp. 76-86, 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014, Princeton, NJ, United States, 1/12/14. https://doi.org/10.1145/2554797.2554807

}

TY - GEN

T1 - Locally testable codes and cayley graphs

AU - Gopalan, Parikshit

AU - Vadhan, Salil

AU - Zhou, Yuan

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We give two new characterizations of (F2 -linear, smooth) locally testable error-correcting codes in terms of Cayley graphs over F 2h: 1. A locally testable code is equivalent to a Cayley graph over F2h whose set of generators is significantly larger than h and has no short linear dependencies, but yields a shortest-path metric that embeds into l1 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 l1. 2. A locally testable code is equivalent to a Cayley graph over F2h 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.

AB - We give two new characterizations of (F2 -linear, smooth) locally testable error-correcting codes in terms of Cayley graphs over F 2h: 1. A locally testable code is equivalent to a Cayley graph over F2h whose set of generators is significantly larger than h and has no short linear dependencies, but yields a shortest-path metric that embeds into l1 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 l1. 2. A locally testable code is equivalent to a Cayley graph over F2h 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.

KW - Cayley graphs

KW - Fourier analysis

KW - Locally testable codes

KW - Metric embeddings

KW - Spectral graph theory

UR - http://www.scopus.com/inward/record.url?scp=84893228804&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893228804&partnerID=8YFLogxK

U2 - 10.1145/2554797.2554807

DO - 10.1145/2554797.2554807

M3 - Conference contribution

AN - SCOPUS:84893228804

SN - 9781450322430

T3 - ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science

SP - 76

EP - 86

BT - ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science

PB - Association for Computing Machinery,

ER -