### DIMACS Theoretical Computer Science Seminar

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