Seminar Details
Approximate Affine Invariance and Distance to Polynomials
- Start Date: October 16, 2017
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Swastik Kopparty - Rutgers University
- Event Location: Hill Center-Room 705
- Presentation Type: Stand Alone Presentation
- Abstract:
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.