Locally testable codes and Cayley graphs

DOI10.1145/2554797.2554807MaRDI QIDQ2988869zbMATHOpenAlexFDO

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)

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

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)

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}

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

Cites work

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

Cited in

(5)

• Local Decoding and Testing for Homomorphisms
• scientific article; zbMATH DE number 1256714 (Why is no real title available?)
• On graphs and codes preserved by edge local complementation
• Robust locally testable codes and products of codes
• 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)