On list decoding of certain \(\mathbb{F}_q\)-linear codes (Q2068823)

Denote by \(C_q^s(m, d)\) the generalization of Reed-Solomon \(s\)-code. A list decoding algorithm for \(\mathbb{F}_q\)-linear codes that generalize the Reed-Solomon \(s\)-codes is found. In the course of the proof a deduction of a statement which helps the improvement of the bound on the minimum distance of the \(C_q^s(m, d)\) codes is shown. For integers \(q,s\)-powers of a prime \(p,\) and a positive numbers \(m\geq 2\) and \(d\) satisfying \(d\leq sq -m-2(s-1)\) and \(m + s \leq q,\) define the integer \(\widetilde{d}= q^{m-1}(s-1 + \frac{q-1}{q}(m + d-1)\) and fixed an integer parameter \(\varphi\geq 3.\) Then there exist a list decoding algorithm that is proved to has runtime \(\text{poly}\left(q^m,\left(\varphi \sqrt{sqm/\widetilde{d}}\right)^{s^m}\right)\) and the list size is shown that can be bounded by \(O\left(\varphi \sqrt{sqm/\widetilde{d}}\right)^{s^m}.\) A brief explanation of each step of the algorithm as well as an analysis of the important aspects of some of its steps are given in more details.