Generalized Reed-Solomon codes over number fields and exact gradient coding

Irwansyah; Intan Muchtadi-Alamsyah; Fajar Yuliawan; Muhammad Irfan Hidayat; Irwansyah; Intan Muchtadi-Alamsyah; Fajar Yuliawan; Muhammad Irfan Hidayat

doi:10.3934/math.2024464

AIMS Mathematics

2024, Volume 9, Issue 4: 9508-9518. doi: 10.3934/math.2024464

Previous Article Next Article

Research article Special Issues

Generalized Reed-Solomon codes over number fields and exact gradient coding

1.
Department of Mathematics, Faculty of Mathematics and Natural Sciences, University of Mataram, Indonesia
2.
Algebra Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia

Received: 31 December 2023 Revised: 09 February 2024 Accepted: 20 February 2024 Published: 07 March 2024
MSC : 11T71, 68P30

This paper describes generalized Reed-Solomon (GRS) codes over number fields that are invariant under certain permutations. We call these codes generalized quasi-cyclic (GQC) GRS codes. Moreover, we describe an application of GQC GRS codes over number fields to exact gradient coding.
- generalized Reed-Solomon codes,
- generalized quasi-cyclic codes,
- number fields,
- Galois group,
- exact gradient coding
Citation: Irwansyah, Intan Muchtadi-Alamsyah, Fajar Yuliawan, Muhammad Irfan Hidayat. Generalized Reed-Solomon codes over number fields and exact gradient coding[J]. AIMS Mathematics, 2024, 9(4): 9508-9518. doi: 10.3934/math.2024464

Related Papers:

Abstract

This paper describes generalized Reed-Solomon (GRS) codes over number fields that are invariant under certain permutations. We call these codes generalized quasi-cyclic (GQC) GRS codes. Moreover, we describe an application of GQC GRS codes over number fields to exact gradient coding.

References

[1]	A. Dür, The automorphism groups of Reed-Solomon codes, J. Comb. Theory A, 44 (1987), 69–82. https://doi.org/10.1016/0097-3165(87)90060-4 doi: 10.1016/0097-3165(87)90060-4
[2]	S. Dutta, V. Cadambe, P. Grover, Short-dot: Computing large linear transforms distributedly using coded short dot products, IEEE T. Inform. Theory, 65 (2019), 6171–6193. https://doi.org/10.1109/TIT.2019.2927558 doi: 10.1109/TIT.2019.2927558
[3]	C. Güneri, F. Özbudak, B. Özkaya, E. Sacikara, Z. Sepasdar, P. Solé, Structure and performance of generalized quasi-cyclic codes, Finite Fields Th. App., 47 (2017), 183–202. https://doi.org/10.1016/j.ffa.2017.06.005 doi: 10.1016/j.ffa.2017.06.005
[4]	W. Halbawi, Error-correcting codes for networks, storage, and computation, PhD Thesis, California Institute of Technology, 2017. https://doi.org/10.7907/Z9J67F08
[5]	S. Kalyanswamy, Inverse Galois problem for totally real number fields, PhD Thesis, Cornell University, 2012.
[6]	T. Kasami, A Gilberd-Varshamov bound for quasi cyclic codes of rate $1/2$, IEEE T. Inform. Theory, 20 (1974), 679. https://doi.org/10.1109/TIT.1974.1055262 doi: 10.1109/TIT.1974.1055262
[7]	S. Loepp, W. K. Wooters, Protecting information: from classical error correction to quantum cryptography, Cambridge: Cambridge University Press, 2006. https://doi.org/10.1017/CBO9780511813719
[8]	M. Li, D. G. Andersen, A. Smola, K. Yu, Communication efficient distributed machine learning with the parameter server, Proceedings of the 27th International Conference on Neural Information Processing Systems, 1 (2014), 19–27.
[9]	I. Márquez-Corbella, R. Pellikaan, A characterization of MDS codes that have an error-correcting pair, Finite Fields Th. App., 40, (2016), 224–245. https://doi.org/10.1016/j.ffa.2016.04.004
[10]	I. Muchtadi-Alamsyah, Irwansyah, A. Barra, Generalized quasi-cyclic codes with arbitrary block lengths, Bull. Malays. Math. Sci. Soc., 45 (2022), 1383–1407. https://doi.org/10.1007/s40840-022-01251-x doi: 10.1007/s40840-022-01251-x
[11]	N. Raviv, I. Tamo, R. Tandon, A. G. Dimakis, Gradient coding from cyclic MDS codes and expander graph, IEEE T. Inform. Theory, 66 (2020), 7475–7489. https://doi.org/10.1109/TIT.2020.3029396 doi: 10.1109/TIT.2020.3029396
[12]	G. E. Séguin, The algebraic structure of codes invariant under a permutation, In: Information theory and applications II, Heidelberg: Springer, 1995, 1–18. https://doi.org/10.1007/BFb0025131
[13]	I. Siap, N. Kulhan, The structure of generalized quasi-cyclic codes, Appl. Math. E-Notes, 5 (2005), 24–30.
[14]	R. Tandon, Q. Lei, A. Dimakis, N. Karampatziakis, Gradient coding: Avoiding stragglers in distributed learning, Proceedings of the 34th International Conference on Machine Learning, 70 (2017), 3368–3376.
[15]	H. G. J. Tiesinga, The inverse Galois problem, PhD Thesis, University of Groningen, 2016. Available from:
[16]	N. J. Yadwarkar, B. Hariharan, J. E. Gonzales, R. Katz, Multitask learning for straggler avoiding predictive job scheduling, J. Mach. Learn. Res., 17 (2016), 3692–728.

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)