Combinatorics Seminar
When: Sunday, December 7, 10am
Where: Schreiber 309
Speaker: Shachar Lovett, Weizmann Institute
Title: Approximation and calculation for low-degree
polynomials
Abstract:
We study the model of approximation and calculation of
multivariate low-degree polynomials over finite fields, by lower
degree polynomials. We prove that the models are in fact equivalent
for constant degree polynomials - if a constant degree polynomial can
be non-trivially approximated by a lower degree polynomial, then it
can be exactly computed by a constant number of lower degree
polynomials.
This work is in fact a generalization of a work by Green & Tao.
They show this result for polynomials of degree at most the size
of the field, and we generalize their result to all fields (and in
particular to F_2, where the original result by Green&Tao is
meaningless).
Joint work with Tali Kaufman.