Seminars & Colloquia Calendar
Approximate affine invariance and distance to polynomials
Swastik Kopparty, Rutgers University
Location: HILL 705
Date & time: Monday, 16 October 2017 at 2:00PM - 3:00PM
Let F be a finite field, and let V be the set of functions from F to F computed by a univariate polynomial of degree at most d. It is easy to see that V is closed under affine transformations: i.e., if g(X) is in V, then so is h(X) = g(aX+b). V is also closed under taking linear combinations. We will study what happens to functions *not in V* when we apply random affine transformations and take random linear combinations of these. Our main result is that these operations increase the distance to V very quickly.
Joint work with Eli Ben-Sasson and Shubhangi Saraf