Left-right Cayley complex code[1]
Description
Binary code constructed on a left-right Cayley complex using a pair of base codes \(C_A,C_B\) and an expander graph [2] such that codewords for a fixed graph vertex are codewords of the tensor code \(C_A \otimes C_B\). A family of such codes is one of the first \(c^3\)-LTCs.
Parent
- Binary linear LTC — Left-right Cayley complex codes yield one of the first two families of \(c^3\)-LTCs.
Cousins
- Tensor-product code — Left-right Cayley complex codewords for a fixed graph vertex are codewords of a tensor code.
- Expander code — Left-right Cayley complex codes can be viewed as Tanner-like codes on expander graphs [2], but with bits defined on squares and constraints on edges (as opposed to edges and vertices, respectively, for expander codes). Expander codes are also typically not locally testable [3].
- Balanced product (BP) code — Left-right Cayley complexes can be obtained via a balanced product of \(G\)-graphs [1].
- Quantum Tanner code — Applying the CSS construction to two left-right Cayley complex codes yields quantum Tanner codes, and one can simultaneously prove a linear distance for the quantum code and local testability for one of its constituent classical codes [4].
References
- [1]
- I. Dinur et al., “Locally Testable Codes with constant rate, distance, and locality”, (2021) arXiv:2111.04808
- [2]
- S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
- [3]
- E. Ben-Sasson, P. Harsha, and S. Raskhodnikova, “Some 3CNF properties are hard to test”, Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC ’03 (2003) DOI
- [4]
- A. Leverrier and G. Zémor, “Quantum Tanner codes”, (2022) arXiv:2202.13641
Page edit log
- Victor V. Albert (2022-09-29) — most recent
Cite as:
“Left-right Cayley complex code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/lr-cayley-complex