Sparse Polynomial Interpolation Codes and their
List-Decoding Beyond Half the Minimum Distance
|Speaker:||Erich Kaltofen (NCSU)
||Thursday, April 28, 2016
||12:00pm - 1:00pm
||D344 LSRC, Duke
We present algorithms for performing sparse univariate
polynomial interpolation with errors in the evaluations of
the polynomial. The interpolation algorithms use as a
substep the Prony-Blahut algorithm, and correct errors by
subsampling at an arithmetic progression of sample indices.
The sparse interpolation problem with errors yields a new
algebraic error-correcting code.
Over finite fields we obtain a polynomial-time list-decoder
in the sense of Guruswami-Sudan for a higher than maximal
error rate. Over the real numbers the maximal uniquely
decodable error rate is much larger by the Descartes' Rule
of Signs. For the latter code over the real numbers, a
polynomial-time decoder for the maximal error rate is not
This is joint work with Clement Pernet, Univ. Grenoble.
Erich Kaltofen received both his Ph.D. degree in Computer
Science in 1982 from Rensselaer Polytechnic Institute. He
was an Assistant Professor of Computer Science at the
University of Toronto and an Assistant, Associate, and full
Professor at Rensselaer Polytechnic Institute. Since 1996
he is a Professor of Mathematics at North Carolina State
University. He has visiting positions at ENS Lyon, MIT,
UPMC Paris, U. Grenoble, and U. Waterloo.
Kaltofen's current interests in the symbolic computation
discipline are hybrid symbolic/numeric algorithms, efficient
algorithms for sparse interpolation and error correction
and interactive proofs. Kaltofen has designed
several algorithms for polynomial factorization including
one for polynomials in staight-line representation.
Kaltofen was the Chair of ACM's Special Interest Group on
Symbolic & Algebraic Manipulation 1993 - 95. From 1985 - 87
he held an IBM Faculty Development Award. In 2009 Kaltofen
was selected an ACM Fellow.
He has edited 4 books, including the Computer Algebra
Handbook in 2002, published over 160 research articles.
According to Microsoft Academic Search, Kaltofen is a
Hosted by: Debmalya Panigrahi