The Taub Faculty of Computer Science Events and Talks

We study the complexity of powering in GF(2^n) by constant depth arithmetic circuits over GF(2) (also known as AC0(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.

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

Our proof revisits the classical Razborov-Smolensky method for circuit lower bounds, and executes an analogue of it in the land of univariate polynomials over GF(2^n).