Mathematics Colloquium by Dr. Erick Kaltofen, North Carolina State University

Event Details
  • Date/Time:
    • Thursday March 16, 2017 - Friday March 17, 2017
      11:00 am - 11:59 am
  • Location: Skiles Building, Room 006
  • Phone: 404-894-2700
  • URL: School of Mathematics
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: Title: Sparse Polynomial Interpolation Without and With Errors

Full Summary: No summary paragraph submitted.

We present algorithms for performing sparse univariate polynomial interpolation with errors in the evaluations of the polynomial. Our interpolation algorithms use as a substep an algorithm that originally is by R. Prony from the French Revolution (Year III, 1795) for interpolating exponential sums and which is rediscovered to decode digital error correcting BCH codes over finite fields (1960). Since Prony's algorithm is quite simple, we will give a complete description, as an alternative for Lagrange/Newton interpolation for sparse polynomials. When very few errors in the evaluations are permitted, multiple sparse interpolants are possible over finite fields or the complex numbers, but not over the real numbers. The problem is then a simple example of list-decoding in the sense of Guruswami-Sudan. Finally, we present a connection to the Erdoes-Turan Conjecture (Szemeredi's Theorem). This is joint work with Clement Pernet, Univ. Grenoble.

Additional Information

In Campus Calendar

School of Mathematics

Invited Audience
Faculty/Staff, Public, Undergraduate students, Graduate students
  • Created By: sm17
  • Workflow Status: Published
  • Created On: Mar 3, 2017 - 4:04pm
  • Last Updated: Apr 13, 2017 - 5:12pm