Title: Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions

Advisors: Paul Beame and Shayan Oveis Gharan

Abstract: We develop an extension of recent analytic methods for obtaining time-space tradeoff lower bounds for problems of learning from uniform random test samples. With our methods we can obtain bounds for general finite learning problems in which the space of tests can be significantly smaller than the space of inputs and the feedback from each test can come from an arbitrary finite set.

As applications that follow from our new techniques, we show that any algorithm that learns m-variate polynomial functions of degree at most d over F_2 with success at least 2^O(m) from evaluations on randomly chosen inputs either requires space \Omega(mn/d) or 2^{\Omega(m/d)} time where n = (m/d)^{\theta(d)} is the dimension of the space of such polynomials. We also extend these results to learning linear and quadratic polynomials over any odd prime field F_p.
CSE 303
Tuesday, November 28, 2017 - 13:30 to 15:00