# 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.