Applying Coding Theory to Sparse Interpolation

DOI10.1137/0222046MaRDI QIDQ3137705zbMATH OpenOpenAlexFDO

Authors

Publication date 10 October 1993

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0222046

zbMATH Keywords

interpolationfinite fieldReed-Solomon codesBoolean polynomialsReed-Muller codesfast interpolation algorithmssparse multivariate polynomialslinear sums of characters

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Finite fields (field-theoretic aspects) (12E20) Linear codes (general theory) (94B05) Arithmetic theory of polynomial rings over finite fields (11T55) Number-theoretic algorithms; complexity (11Y16) Semigroups (20M99)

Recommendations

• The interpolation problem for \(k\)-sparse polynomials and character sums
• Sparse interpolation over finite fields via low-order roots of unity
• On zero-testing and interpolation of sums of characters
• The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators
• Interpolation in list decoding of Reed-Solomon codes

Cited in

(3)

• The interpolation problem for \(k\)-sparse polynomials and character sums
• Almost optimal proper learning and testing polynomials
• The complexity of sparse polynomial interpolation over finite fields

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)