Loading...
Please wait, while we are loading the content...
Similar Documents
C C ] 23 A ug 2 01 3 Locally Testable Codes and Cayley Graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Gopalan, Parikshit Vadhan, Salil P. Zhou, Yuan Sheng |
| Copyright Year | 2018 |
| Abstract | We give two new characterizations of ( F2-linear) locally testable error-correcting codes in terms of Cayley graphs over F 2 : 1. A locally testable code is equivalent to a Cayley graph ove r F 2 whose set of generators is significantly larger thanh and has no short linear dependencies, but yields a shortestpath metric that embeds intol1 with constant distortion. This extends and gives a converse to a result of Khot and Naor (2006), which showed that codes with large dual distanc e imply Cayley graphs that have no low-distortion embeddings into l1. 2. A locally testable code is equivalent to a Cayley graph ove r F 2 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 t o a recent construction of Barak et al. (2012), which showed that locally testable codes imply Cayl ey graphs that are small-set expanders but have many large eigenvalues. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://salil.seas.harvard.edu/files/salil/files/1308.5158.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
