Algorithms Seminar

Sparse Polynomial Interpolation Codes and their List-Decoding Beyond Half the Minimum Distance

Speaker:Erich Kaltofen (NCSU)
Date: Thursday, April 28, 2016
Time: 12:00pm - 1:00pm
Location: 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 known. 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 top-ranked author:

Hosted by:
Debmalya Panigrahi