Gopalan, ParikshitVadhan, SalilZhou, Yuan2018-01-052014Gopalan, Parikshit, Salil Vadhan, and Yuan Zhou. 2014. “Locally Testable Codes and Cayley Graphs.” In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS’14), 12-14 January, 2014, Princeton, NJ, 81-92. New York, NY: ACM Press. doi:10.1145/2554797.2554807.978-1-4503-2698-8http://nrs.harvard.edu/urn-3:HUL.InstRepos:34604533We give two new characterizations of ( 2-linear, smooth) locally testable error-correcting codes in terms of Cayley graphs over Fh2: * A locally testable code is equivalent to a Cayley graph over h2 whose set of generators is significantly larger than h and has no short linear dependencies, bbut yields a shortest-path metric that embeds into l 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 . * A locally testable code is equivalent to a Cayley graph over Fh2 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.en-USConference Paper2013-12-18Kobbi Nissim, Salil Vadhan, David Xiao2018-01-0510.1145/2554797.2554807