Chaoping Xing

MDS codes have garnered significant attention due to their wide applications in practice. To date, most known MDS codes are equivalent to Reed–Solomon codes. The construction of non-Reed–Solomon (non-RS) type MDS codes has emerged as an intriguing and important problem in both coding theory and finite geometry. Although some constructions of non-RS type MDS codes have been presented in the literature, the parameters of these MDS codes remain subject to strict constraints. In this paper, we introduce a general framework of constructing $[n,k]$ MDS codes using the idea of selecting a suitable set of evaluation polynomials and a set of evaluation points such that all nonzero polynomials have at most $k-1$ zeros in the evaluation set. Moreover, these MDS codes can be proved to be non-Reed–Solomon by computing their Schur squares. Furthermore, several explicit constructions of non-RS MDS codes are given by converting to combinatorial problems. As a result, new families of non-RS MDS codes with much more flexible lengths can be obtained and most of them are not covered by the known results.

Code-based Distributed Matrix Multiplication (DMM) has been widely studied as an effective method for large-scale matrix computations in distributed systems. Two central challenges in code-based DMM are minimizing the communication cost and reducing the recovery threshold—the minimum number of worker nodes required to successfully recover the matrix multiplication. Several Reed-Solomon (RS)-based schemes, including Polynomial, MatDot, and PolyDot codes, have been proposed; however, their applicability is constrained by the size of the underlying finite field, limiting the number of usable worker nodes. Algebraic geometry (AG) codes, as a generalization of RS codes, overcome this limitation by enabling longer code lengths over small fields. Prior work has generalized Polynomial and MatDot codes to AG codes, achieving recovery thresholds that increase additively with the genus of the underlying algebraic function field. However, extending PolyDot codes to AG settings with a similar additive increase has remained an open challenge, due to the more complex structure of functions on algebraic curves compared to univariate polynomials. In this work, we generalize RS-based Polynomial, MatDot, and PolyDot codes under a unified AG framework based on local expansions of functions. Our main contribution is the first construction of AG-based PolyDot codes with recovery thresholds that scale additively with the genus. Moreover, our AG-based Polynomial and MatDot codes achieve better recovery thresholds than existing AG-based DMM schemes, while maintaining comparable communication costs. A key innovation of our construction is a novel basis for the Riemann–Roch space, derived from local expansions, which avoids the cancellation issues caused by using non-gap numbers in prior constructions.

Encoding and decoding of Reed-Muller codes have been a major research topic in coding and theoretical computer science communities. Despite of the fact that there have been numerous encoding and decoding algorithms in the literature, most of them are not quasi-linear time algorithms for arbitrary order Reed-Muller codes. Under the decoding framework proposed by Pellikaan and Wu (IEEE TIT, 2004) which regards Reed-Muller codes as subfield subcodes of Reed-Solomon codes, we propose a new decoding algorithm for Reed-Muller codes that improves previous polynomial decoding complexity to quasilinear complexity. Our new decoding algorithm includes multivariate multipoint evaluation (MPE) and interpolation under a new basis of the multivariate polynomial space as two main steps. We show that the MPE and interpolation at certain multipoint sets can be performed in quasi-linear time as well. Our approach is based on a well-known transform between univariate polynomials and multivariate polynomials. We make use of the key fact that the transformation matrix between univariate polynomials and multivariate polynomials is sparse. Due to sparsity, MPE and interpolation of multivariate polynomials and decoding of Reed-Muller codes can be reduced to MPE and interpolation of univariate polynomials and decoding of Reed-Solomon codes without extra cost respectively, i.e, the complexity of MPE and interpolation of multivariate polynomials (and, respectively, decoding of Reed-Muller codes) is dominated by that of MPE and interpolation of univariate polynomials (and, respectively, decoding of Reed-Solomon codes). As a result of this reduction, we obtain our quasi-linear time algorithms.

Coded Distributed Matrix Multiplication (CDMM) is a distributed matrix multiplication (DMM) for large-scale matrices through a coding scheme such that any R worker nodes among all N worker nodes can recover the final product, where N corresponds to the length of the code and R ≤ N is called the recovery threshold. The state-of-art CDMM schemes, such as EP codes for Single DMM and GCSA codes for batch DMM, are defined over a Galois field GF(q) of size q ≥ N. These are inefficient for small Galois fields such as GF(2) and the integer residue ring Z_p^ℓ due to the lack of invertible elements for interpolation. DMM over Z_p^ℓ (such as Z₂⁶⁴ ) is well-motivated in practice due to their direct compatibility with hardware. In this work, we construct efficient CDMM over the Galois ring GR(p^ℓ, d) which is an extension ring over Z_p^ℓ of degree d, particularly, GR(p, d) = GF(p^d) is the Galois field and GR(_p^ℓ, 1) = Z_p^ℓ. We first give a general CDMM framework for the batch of n matrix multiplications via the famous RMFE (Cascudo et al. Crypto’18). Compared with GCSA, our construction has a smaller recovery threshold by a factor of 1/n. Next, we optimize EP codes via batch preprocessing of the input matrices. We give two types of Single CDMM, which can achieve almost the same performance as EP codes over a Galois field with size q ≥ N. Finally, we present the experimental analysis of our CDMM on Galois rings.