TY  - JOUR
T1  - Asymptotically good homological error correcting codes
AU  - Mccullough, Jason
AU  - Newman, Heather
PY  - 2019
DA  - September
DO  - 10.13069/jacodesmath.617235
JF  - Journal of Algebra Combinatorics Discrete Structures and Applications
PB  - iPeak Academy
WT  - DergiPark
SN  - 2148-838X
SP  - 135
EP  - 145
VL  - 6
IS  - 3
LA  - en
AB  - Let $\Delta$ be an abstract simplicial complex. We study classical homological error correcting codes associated to $\Delta$, which generalize the cycle codes of simple graphs.  It is well-known that cycle codes of graphs do not yield asymptotically good families of codes.  We show that asymptotically good families of codes do exist for homological codes associated to simplicial complexes of dimension at least $2$. We also prove general bounds and formulas for (co-)cycle and (co-)boundary codes for arbitrary simplicial complexes over arbitrary fields.
KW  - Error correcting codes
KW  - Simplicial complexes
KW  - Simplicial homology
CR  - [1] N. Alon, S. Hoory, N. Linial, The Moore bound for irregular graphs, Graphs Combin. 18(1) (2002)
53–57.
CR  - [2] L. Aronshtam, N. Linial, T. Łuczak, R. Meshulam, Collapsibility and vanishing of top homology in
random simplicial complexes, Discrete Comput. Geom. 49(2) (2013) 317–334.
CR  - [3] A. R. Calderbank, P. W. Shor, Good quantum error–correcting codes exist, Physical Review A 54(2)
(1996) 1098–1105.
CR  - [4] D. Dotterrer, L. Guth, M. Kahle 2–complexes with large 2–girth, Discrete Computational Geometry
59(2) (2018) 383–412.
CR  - [5] R. G. Gallager, Low–density parity–check codes, IRE Trans. 8(1) (1962) 21–28.
CR  - [6] R. G. Gallager, Low–Density Parity–Check Code, MIT Press, 1963.
CR  - [7] X.-Y. Hu, E. Eleftheriou, D. M. Arnold, Regular and irregular progressive edge–growth Tanner
graphs, IEEE Trans. Inform. Theory 51(1) (2005) 386–398.
CR  - [8] Steven Roman, Coding and Information Theory, Graduate Texts in Mathematics, vol. 134, Springer–
Verlag, New York, 1992.
CR  - [9] Pavel Rytír, Geometric representations of linear codes, Adv. Math. 282(10) (2015) 1–22.
CR  - [10] Charles Saltzer, Topological codes, Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madison,
Wis., 1968), Wiley, New York (1968) 111–129.
CR  - [11] P. W. Shor, Scheme for reducing decoherence in quantum memory, Phys. Rev. A. 52(4) (1995)
R2493–R2496.
CR  - [12] A. M. Steane, Multiple–particle interference and quantum error correction, Proc. Roy. Soc. A.
452(1954) (1996) 2551–2577.
CR  - [13] S. Thomeier, Error–correcting polyhedral codes, J. Comput. Inform. 1(2) (1990) 91–101.
CR  - [14] G. Zémor, On Cayley graphs, surface codes, and the limits of homological coding for quantum error
correction, Coding and cryptology, Lecture Notes in Comput. Sci., vol. 5557, Springer, Berlin (2009)
259–273.
UR  - https://doi.org/10.13069/jacodesmath.617235
L1  - https://dergipark.org.tr/tr/download/article-file/803259
ER  -