The performance of Reed–Solomon codes (RS codes, for short) in the presence of insertion and deletion errors has attracted growing attention in recent literature. In this work, we further study this intriguing mathematical problem, focusing on two regimes. First, we study the question of how wellfull-lengthRS codes perform against insertions and deletions. For 2-dimensional RS codes, we provide a complete characterization of codes that cannot correct even a single insertion or deletion. Furthermore, we prove that for sufficiently large field sizeq, nearly all full-length 2-dimensional RS codes can correct up to (1 - δ)qinsertion and deletion errors for any 0k≥ 2, there exists a full-lengthk-dimensional RS code capable of correctingq/(10k) insertion and deletion errors, providedqis large enough. Second, we focus on rate-1/2 RS codes that can correct a single insertion or deletion error. We present a polynomial-time algorithm that constructs such codes over fields of sizeq= Θ(k4). This result matches the existential bound given in [1].

In this paper we consider algebraic geometry (AG) codes: a class of codes constructed from algebraic codes (equivalently, using function fields) by Goppa. These codes can be list-decoded using the famous Guruswami-Sudan (GS) list-decoder, but the genus g of the used function field gives rise to negative term in the decoding radius, which we call the genus penalty. In this article, we present a GS-like list-decoding algorithm for arbitrary AG codes, which we call the inseparable GS list-decoder. Apart from the multiplicity parameter s and designed list size$\ell $, common for the GS list-decoder, we introduce an inseparability exponent e. Choosing this exponent to be positive gives rise to a list-decoder for which the genus penalty is reduced with a factor$1/p^{e}$compared to the usual GS list-decoder. Here p is the characteristic. Our list-decoder can be executed in$\tilde {\mathcal {O}} (s\ell ^{\omega }\mu ^{\omega -1}p^{e}(n+g))$field operations, where n is the code length and$\tilde {\mathcal {O}} $means that logarithmic factors are ignored.

A Locally Recoverable Code is a code such that the value of any single coordinate of a codeword can be recovered from the values of a small subset of other coordinates. When we have δ non-overlapping subsets of cardinality ri that can be used to recover the missing coordinate we say that a linear code C with length n, dimension k, minimum distance d has (r1, . . . , rδ)locality and denote by [n, k, d; r1, r2, . . . , rδ]. In this paper we provide a new upper bound for the minimum distance of these codes. Working with a finite number of subgroups of cardinality ri+ 1 of the automorphism group of a function field F|Fqof genus g ≥ 1 we propose a construction of [n, k, d; r1, r2, . . . , rδ]-codes and apply the results to some well known families of function fields.