MINI-WORKSHOP ON PSEUDORANDOMNESS

Submitted by admin on Wed, 01/09/2013 - 19:01
The Correlation of Multiplicative Characters with Polynomials over Finite Fields
Swastik Kopparty
Member, School of Mathematics
Date & Time: 
Fri, 04/22/2011 - 11:30 - 12:30
Location: 
S-101

This talk will focus on the complexity of the cubic-residue (and higher-residue) characters over GF(2^n) , in the context of both arithmetic circuits and polynomials.
We show that no subexponential-size, constant-depth arithmetic circuit over GF(2) can correctly compute the cubic-residue character for more than 1/3 + o(1) fraction of the elements of GF(2^n). The key ingredient in the proof is an adaptation of the Razborov-Smolensky method for circuit lower bounds to setting of univariate polynomials over GF(2^n) .
As a corollary, we show 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} . Classical approaches based on van der Corput differencing and the Weil bounds show this for d << log(n).

Note: 
<a href="http://math.ias.edu/files/seminars/PseudorandomnessMiniWkshp.pdf">http://math.ias.edu/files/seminars/PseudorandomnessMiniWkshp.pdf</a>
terms: