Combinatorics Seminar- Efficient low-degree polynomial interpolation

Speaker: Alexander Barg, University of Maryland
Date and time: Wednesday, November 29, 4-5pm
Place: Rome 771
Title: Efficient low-degree polynomial interpolation
Abstract: Let f(x) be a polynomial of degree less than k over a finite field Fq. Its value at any given point a in Fq can be found once we know its values at any k other points a_i.  We consider the problem of finding f(a) by observing some partial information about the values of f(x) at d > k points, i.e., some functions g_i(a_i), i=j_1,...,j_d.  We present a construction that gives an optimal solution of this problem (we will discuss the meaning of optimality along the way). The construction relies on specially designed subfields of Fq.  This problem is known in coding theory as the repair problem of Reed-Solomon codes, and we will use coding theoretic language in the description of the solution.  Based on recent joint works with Itzhak Tamo and Min Ye.