Locally testable codes and Cayley graphs

DOI10.1145/2554797.2554807zbMATH Open1364.94753arXiv1308.5158OpenAlexW2104333656MaRDI QIDQ2988869FDOQ2988869

Authors: Parikshit Gopalan, Yuan Zhou, Salil Vadhan 

Publication date: 19 May 2017

Published in: Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Abstract: We give two new characterizations of ($F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $F_2^h$: �egin{enumerate} item A locally testable code is equivalent to a Cayley graph over $F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a shortest-path metric that embeds into $el{l}_1$ 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 $el{l}_1$. item A locally testable code is equivalent to a Cayley graph over $F_2^h$ 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. end{enumerate}

Full work available at URL: https://arxiv.org/abs/1308.5158

Recommendations

• A combinatorial characterization of smooth LTCs and applications
• On coset leader graphs of structured linear codes
• Locally Testable Cyclic Codes
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Locally testable codes and PCPs of almost-linear length

zbMATH Keywords

spectral graph theoryCayley graphsFourier analysislocally testable codesmetric embeddings

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Other types of codes (94B60)

Cites Work

• A hierarchy of polynomial time lattice basis reduction algorithms
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Evaluating Branching Programs on Encrypted Data
• Fully homomorphic encryption using ideal lattices
• Public-key cryptosystems from the worst-case shortest vector problem
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• On lattices, learning with errors, random linear codes, and cryptography
• Trapdoors for hard lattices and new cryptographic constructions
• Title not available (Why is that?)
• (Leveled) fully homomorphic encryption without bootstrapping
• On lattices, learning with errors, random linear codes, and cryptography
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Trapdoors for lattices: simpler, tighter, faster, smaller
• Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
• New lattice-based cryptographic constructions
• Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
• Toward basing fully homomorphic encryption on worst-case hardness

Cited In (5)

• Title not available (Why is that?)
• Robust locally testable codes and products of codes
• Local Decoding and Testing for Homomorphisms
• On graphs and codes preserved by edge local complementation
• Locally Testable Cyclic Codes

This page was built for publication: Locally testable codes and Cayley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988869)