Title: Approximate affine invariance and distance to polynomials
Speaker: Swastik Kopparty, Rutgers University
Date: Monday, October 16, 2017 2:00 pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
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