Applying Coding Theory to Sparse Interpolation

From MaRDI portal





Let \(A\) be an abelian monoid with neutral element \(1_ A\) and let \(K\) be a field. The set \(\Hom(A, (K,*))\) of all characters is a linearly independent subset of the \(K\)-space of all maps from \(A\) into \(K\). For any subset \(X\subseteq \Hom(A, (K,*))\) and a positive integer \(k\) the set \(X_ k\) of \(k\)-sums of characters from \(X\) is the set of linear sums of characters over \(K\) with at most \(k\) nonzero terms. The interpolation problem of interest is to determine a procedure by which, for any \(f=\sum_ \chi f_ \chi\), \(\chi\in X_ k\), its support and coefficients can be determined from as few evaluations of \(f\) as possible. Fast interpolation algorithms are given for sparse sums of these characters on the product monoid \(U^ n\) in two special cases. In the first case \(U\) is a finite cyclic group of order \(e\) and \(K\) is a finite field with an \(e\)th root of unity. The interpolation algorithm in this case involves Reed-Solomon codes. In the second case, \(K\) is the binary field \(GF(2)\) and \(U\) the multiplicative monoid of \(GF(2)\). In this case sparse sums of characters coincide with sparse Boolean polynomials and can be interpolated using the smallest set of evaluation points by decoding Reed-Muller codes.











This page was built for publication: Applying Coding Theory to Sparse Interpolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3137705)