Sparse polynomial interpolation codes and their decoding beyond half the minimum distance
Sparse polynomial interpolation codes and their decoding beyond half the minimum distance
复制标题
超过最小距离一半的稀疏多项式插值码及其解码
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Clément Pernet
中科院分区：
文献类型：
--
作者：
E. Kaltofen;Clément Pernet
我们提出的算法是根据Comer，Kaltofen和Pernet的最初工作的稀疏单变量多项式插值。代码字的长度除以两倍的稀疏性。算法达到最小距离。
我们的新的多项式时间列表解码算法使用算术进程索引的接收评估的子序列，允许对较大半径的解码，也就是说，在返回候选者稀疏的多项式列表的同时，评估中有更多的错误所有通常的术语数量和误差数量的较小值，并为此改进提供了不对称的分析。错误我们可以从多项式的74个值中列出多项式时间的解码，而我们的早期算法则需要2T（E + 1）= 110评估。
然后，我们在字符零中提出了这些代码的两种变体，在变量的值选择的情况下，可产生更大的最小距离：代码词长度减去稀疏性的两倍。
We present algorithms performing sparse univariate polynomial interpolation with errors in the evaluations of the polynomial. Based on the initial work by Comer, Kaltofen and Pernet [Proc. ISSAC 2012], we define the sparse polynomial interpolation codes and state that their minimal distance is precisely the code-word length divided by twice the sparsity. At ISSAC 2012, we have given a decoding algorithm for as much as half the minimal distance and a list decoding algorithm up to the minimal distance.
Our new polynomial-time list decoding algorithm uses sub-sequences of the received evaluations indexed by an arithmetic progression, allowing the decoding for a larger radius, that is, more errors in the evaluations while returning a list of candidate sparse polynomials. We quantify this improvement for all typically small values of number of terms and number of errors, and provide a worst case asymptotic analysis of this improvement. For instance, for sparsity T = 5 with ≤ 10 errors we can list decode in polynomial-time from 74 values of the polynomial with unknown terms, whereas our earlier algorithm required 2T(E + 1) = 110 evaluations.
We then propose two variations of these codes in characteristic zero, where appropriate choices of values for the variable yield a much larger minimal distance: the code-word length minus twice the sparsity.