| COMPUTER SCIENCE/DISCRETE MATH I | |
| Topic: | Average Case to Worst Case Reductions for Polynomials |
| Speaker: | Shachar Lovett |
| Affiliation: | Hebrew University of Jerusalem |
| Date: | Monday, October 13 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
We study the model of approximation and calculation of constant degree multivariate polynomials over finite fields. We prove that if a constant degree polynomial can be approximated by a function of a constant number of lower degree polynomials, it can in fact be computed exactly by a function of a constant number of lower degree polynomials. This shows that in this model, approximation and exact calculation are qualitatively equivalent. The technical part of the work is a generalization of a theorem of Green & Tao, showing a structure-randomness dichotomy for constant degree multivariate polynomials.