Locally testable codes and cayley graphs

Parikshit Gopalan, Salil Vadhan, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery,
Pages76-86
Number of pages11
ISBN (Print)9781450322430
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 - Princeton, NJ, United States
Duration: Jan 12 2014Jan 14 2014

Publication series

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

Other

Other2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
CountryUnited States
CityPrinceton, NJ
Period1/12/141/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