Two Structural Results for Low Degree Polynomials and Applications

Computer Science/Discrete Mathematics Seminar I
Topic:Two Structural Results for Low Degree Polynomials and Applications
Speaker:Avishay Tal
Affiliation:Weizmann Institute
Date:Monday, March 10
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/2014/0310-AvistayTal

In this talk we will present two structural results concerning low degree polynomials over \(GF(2)\). The first states that for any degree d polynomial \(f\) in \(n\) variables over \(GF(2)\), there exists a subspace of \(GF(2)^n\) with dimension \(\Omega(n^{1/(d − 1)})\) on which \(f\) is constant. This result can be shown to be tight. Using a recursive argument, we obtain our second structural result, showing that any degree \(d\) polynomial \(f\) induces a partition of \(GF(2)^n\) to affine subspaces of dimension \(\Omega(n^{1/(d − 1)!})\), such that \(f\) is constant on each part. Both structural results hold for more than one polynomial. We also consider the algorithmic aspect of these results. Our structural results have various applications to pseudo-randomness and circuit lower bounds, which we will discuss. Joint work with Gil Cohen.