11/03/97 - Ronitt Rubinfeld
Cornell University
Understanding noisy data: the case of polynomials

In this survey talk, we focus on the following problem and natural variants of it:

Given a set of values T = (x_1,f(x_1)),...,(x_n,f(x_n))a parameter and an integer d, find a degree d polynomial p such that p and f agree on at least a fraction of the inputs in T.

This problem has a wide range of applications, including coding theory, probabilistically checkable proof systems, and cryptography. When =1, this is just the problem of polynomial interpolation. The problem was solved by Berlekamp and Welsh in the case that > 1/2 and n is large compared to d . Until recently, this seemed to be a natural barrier since when < 1/2 and n is large compared to d, there may be more than one polynomial which agrees on a fraction of T. However, it turns out that the problem can be solved even when < 1/2. We survey the recent advances on this problem.