CS 789 THEORY SEMINAR [home]

Speaker:    Adam Klivans 
Affiliation: Harvard University
Date:         March 15, 2004
Title:         Learning Polynomials with Many Coefficients

Abstract:

Interpolating a polynomial from a set of data points is a well-studied problem with applications in many fields. Given input/output access to an unknown polynomial, algorithms for multivariate interpolation return a list of coefficients of the unknown polynomial and their associated monomials. In this talk, we will present a simple algorithm for multivariate interpolation by constructing a small set of evaluation points from which any sparse polynomial can be reconstructed. Our algorithm is the first polynomial-time, deterministic solution which works with respect to any sufficiently large finite field.  If the unknown polynomial has $m$ monomials, any interpolation algorithm must run in time at least $m$ just to output a list of the $m$ coefficients. We will show, however, that it is possible to learn representations of polynomials encoding {\it exponentially} many monomials (for example the polynomial $(x_{1} + ... + x_{n})^{n}$ has exponentially many monomials in $n$). To this end we present an algorithm for learning any polynomial whose partial derivatives induce a low-dimensional vector space. This allows us to give the first algorithm for learning polynomial size depth-3 arithmetic circuits (assuming a partition on the variables).

Joint work with Dan Spielman and Amir Shpilka.