Hermitian-lifted codes (Q2657135)

A linear code \(C\subset\mathbb{F}\) of length \(n\) over a finite field \(\mathbb{F}\) is called locally recoverable (LRC) if for any coordinate \(i \in [n]\) there exists a recovery set \(R \subseteq [n]\setminus \{i \}\), such that the \(i\)-th coordinate \(c_i\) of every codeword \(c \in C\) can be recovered from \(\{c_j : j \in R\}\). If for each \(i\in [n]\), there are \(t\) disjoint recovery sets of size at most \(r\), then we say that \(C\) has locality \(r\) and availability \(t\). LRC's with availability are important for both theoretical and practical reasons, such as the distributed storage of information. In this article, the authors introduce a new type of lifted construction from evaluation codes from curves, and they study that construction on the Hermitian curve \(\mathcal{H}_q\) of equation \(x^q+x=y^{q+1}\) over \(q^2\). Lifted codes were introduced by \textit{A. Guo} et al. [in: Proceedings of the 4th conference on innovations in theoretical computer science, ITCS 2013, Berkeley, CA, USA, January 9--12, 2013. New York, NY: Association for Computing Machinery (ACM), 529--539 (2013; Zbl 1364.94606)]. The lift of a univariate evaluation code \(C_0\) to \(m\) variables is the evaluation code corresponding to the set of all \(m\)-variate polynomials whose restriction to every line corresponds to a codeword in \(C_0\). For the Hermitian curve, every line that is not tangent to \(\mathcal{H}_q\) intersects it in exactly \(q+1\) distinct places, while tangent lines intersect \(\mathcal{H}_q\) in exactly one place. Thus, codes from this curve are good candidates for lifting. In this article, the authors introduce the family of curve lifted codes as a variant on the lifted code construction. In this case, they take the lift with respect to a Hermitian curve: the code corresponds to the evaluation on \(\mathcal{H}_q\) of all bivariate polynomials such that the restriction to any line agrees with some low-degree univariate polynomial on the points of \(\mathcal{H}_q\) intersected with that line. In this way, they obtain codes of length \(q^3\), locality \(q\) and availability \(q^2-1\). The most remarkable property is that they have rate lower bounded by a positive constant independent of \(q\), contrary to what happens to usual one-point Hermitian codes, which have rate that tends to zero as \(q\rightarrow\infty\). The article is clear, well written and provides examples that illustrate the results obtained. Perhaps as a joke, in the references we find the authors in lots of cases cited by first names instead of surnames.