On the resilience of polynomials 

Madhu Sudan (Harvard)

The fact that a univariate polynomial of degree d has at most d roots is one of the most basic results in algebra. Yet it has immense implications in the theory of computation, and also in the practice of reliable communication. The ubiquitous Reed-Solomon codes are based on this fact. 

The use of Reed-Solomon codes in practice also depends on the ability to "decode" the efficiently, algorithmically. Briefly, this problem is simply that of ``interpolating'' polynomials from points, while allowing for some errors. Solving this decoding problems ends up using just a few more basic facts from algebra. In this survey-like talk I will describe some of these old algorithmic ideas.