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

Gopalan, P., Vadhan, S., & Zhou, Y. (2014). Locally testable codes and cayley graphs. In 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.

ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, 2014. p. 76-86 (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science).

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

Gopalan, P, Vadhan, S & Zhou, Y 2014, Locally testable codes and cayley graphs. in 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
Gopalan P, Vadhan S, Zhou Y. Locally testable codes and cayley graphs. In ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery,. 2014. p. 76-86. (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science). https://doi.org/10.1145/2554797.2554807
Gopalan, Parikshit ; Vadhan, Salil ; Zhou, Yuan. / Locally testable codes and cayley graphs. ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, 2014. pp. 76-86 (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science).
@inproceedings{a0406e4867144c75932fee7d9f1ed8bd,
title = "Locally testable codes and cayley graphs",
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.",
keywords = "Cayley graphs, Fourier analysis, Locally testable codes, Metric embeddings, Spectral graph theory",
author = "Parikshit Gopalan and Salil Vadhan and Yuan Zhou",
year = "2014",
month = "1",
day = "1",
doi = "10.1145/2554797.2554807",
language = "English (US)",
isbn = "9781450322430",
series = "ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science",
publisher = "Association for Computing Machinery,",
pages = "76--86",
booktitle = "ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science",

}

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 -