Abstract
I will talk about two neoclassical results showing pseudorandom properties of some simple functions over finite fields of small characteristic (such as F_{2^n}). The first result shows that some functions over F_{2^n}, such as the cubic residue character and Trace(x^(1/3)), are uncorrelated with degree n^{0.1} polynomials over F_2. The theorems and proofs are related to the Razborov-Smolensky method for proving lower bounds on arithmetic circuits over F_2. The second result (joint with Eli Ben-Sasson) shows that some other functions, such as Trace(x^7), are nonconstant on subspaces of small dimension, provided F_{2^n} has no large subfields. The proof uses an algebraic expression of the sum-product phenomenon involving properties of "subspace polynomials."