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

Event Details
Contact
No contact information submitted.
Summaries

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
No
Groups

School of Mathematics

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