Date: Monday 22 August 2022
Time: 11:45 am.
Venue: Lecture Hall 5.
Some algebraic questions in coding theory
Computer Science Department, IIT Mumbai.
Given the evaluation of a degree d univariate polynomial on d+1 distinct inputs, it is a well known fact that the polynomial can be recovered uniquely from these evaluations. Moreover, there is an efficient algorithm to do so.
In this talk, we will discuss a few variations/generalizations of this simple fact, where the goal is to recover polynomials from their evaluations (and the evaluations of derivatives in some cases) even when some of the evaluations are erroneous. In addition to being natural questions on their own, these problems are of central importance in algebraic coding theory, and in some cases, have surprisingly simple and beautiful algorithms. We will discuss some of these classical results, and if time permits, also discuss some recent results for this question of 'noisy multivariate polynomial interpolation' with multiplicities on arbitrary product sets.
Based on joint works with Siddharth Bhandari, Prahladh Harsha, Ashutosh Shankar and Madhu Sudan.