Fun Facts about Polynomials, and Applications to Distributed Storage

In this talk I'll discuss two fun (and perhaps surprising) facts about polynomials over finite fields, and I will explain how these facts can be useful in the context of distributed storage.  The first fun fact is about polynomial interpolation.  You may know that if f(x) is a quadratic polynomial, then you can learn f(0) using any three other evaluations of f(x).  But can you learn f(0) using less information?  Fun fact: yes!  That is, over certain fields, the "standard" polynomial interpolation algorithm is not the best way to recover f(0). The second fun fact is about restrictions of multivariate polynomials.  You may know that if f(x,y) is a quadratic polynomial, then the restriction of f(x,y) to any line (for example, f(x, ax + b)) is a quadratic univariate polynomial: aka, any slice of a paraboloid is a parabola.  But is the converse true?  Fun fact: no!  That is, it was shown by Guo, Kopparty and Sudan that over certain fields, there are polynomials f(x,y) whose restrictions to all lines are low-degree, but f(x,y) itself is not -- we extend this result in a few ways to find even more such polynomials.  In the talk I'll explain these fun facts, and also explain why the questions above arise naturally in applications.  No background about finite fields will be assumed.  This talk is based on joint works with Venkat Guruswami, Luna Frank-Fischer and Ray Li.