***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 17th November, 2.15 in Fine Hall 224
 
Speaker: Shubhangi Saraf, IAS.

Title: Noisy interpolation of sparse polynomials, and applications

Abstract: Let f in F_q[x] be a polynomial of degree d < q/2. It is well-known
that f can be uniquely recovered from its values at some 2d points even after
some small fraction of the values are corrupted. In this talk we will 
establish a similar result for sparse polynomials. We show that a k-sparse 
polynomial f in F_q[x] of degree d < q/2 can be recovered from its values 
at O(k) randomly chosen points, even if a small fraction of the values 
of f are adversarially corrupted.

Our proof relies on an iterative technique for analyzing the rank of a random
minor of a matrix. We use the same technique to establish a collection 
of other results on locally decodable codes and rigid matrices.

Based on joint work with Sergey Yekhanin.

                          -----------

Next week: Thanksgiving, no seminar
Week after: Noga Alon

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)