Title: The complexity of powering in finite fields
Speaker: Swastik Kopparty, Institute for Advanced Study
Date: Wednesday, September 7, 2011 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We study the complexity of powering in the finite field GF(2^n) by constant depth arithmetic circuits over GF(2) (also known as AC^0(parity)). Our study encompasses basic arithmetic operations such as computing cube-roots and cubic-residuosity of elements of GF(2^n). Our main result is that these operations require exponential size circuits. The proof revisits the classical Razborov-Smolensky method, and executes an analogue of it in the land of univariate polynomials over GF(2^n).
We also derive strong average-case versions of these results. For example, we show that no subexponential-size, constant-depth, arithmetic circuit over GF(2) can correctly compute the cubic residue symbol for more than 1/3 + o(1) fraction of the elements of GF(2^n). As a corollary, we deduce a character sum bound showing that the cubic residue character over GF(2^n) is uncorrelated with all degree-d n-variate GF(2) polynomials (viewed as functions over GF(2^n) in a natural way), provided d << n^{0.1}.