Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Locally Testable Codes and L1 Embeddings of Cayley Graphs

Speaker  Parikshit Gopalan

Affiliation  Microsoft

Host  Satya Lokam

Duration  01:12:34

Date recorded  16 October 2013

A locally testable code (LTC) is an error correcting code which admits a very efficient procedure for testing membership in the code: a local tester queries few locations in the received word but still distinguishes codewords from words that are far from the code. The main open questions about LTCs are about the tradeoffs possible between rate, distance and query complexity.

We show that the local testability of a binary linear code is related (and in fact equivalent) to the L1 embeddability of a related Cayley graph. Thus one can reformulate existential questions about LTCs as questions about the existance of certain Cayley graphs that admit constant distortion embeddings into L1. We discuss what this tells us about existing results on LTCs and what it might tell us about new results.

Joint work with Salil Vadhan (Harvard) and Yuan Zhou (CMU).

©2013 Microsoft Corporation. All rights reserved.
> Locally Testable Codes and L<sub>1</sub> Embeddings of Cayley Graphs