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 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, 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 [2].
- Balanced product 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 [3].
References
- [1]
- I. Dinur et al., “Locally Testable Codes with constant rate, distance, and locality”, (2021) arXiv:2111.04808
- [2]
- 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
- [3]
- 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