Computer Science/Discrete Mathematics Seminar I

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.