Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Theory Seminar: On the Complexity of Powering in Finite Fields
event speaker icon
Swastik Kopparty (IAS and Rutgers)
event date icon
Wednesday, 6.7.2011, 12:30
event location icon
Taub 601
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).
[Back to the index of events]