### Volume 2016

#### Circuit Complexity of Powering in Fields of Odd Characteristic

School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road, Mumbai 400005, INDIA;
arkadev DOT c AT tifr DOT res DOT in

Frederic Green
Department of Mathematics and Computer Science
Clark University, Worcester, MA 01610;
fgreen AT clarku DOT edu

Howard Straubing
Computer Science Department
Boston College, Chestnut Hill, MA 02467;
straubin AT cs DOT bc DOT edu

August 3, 2016

#### Abstract

By a careful analysis of the proofs of Kopparty in fields of characteristic 2, we show that the problem of powering in $\mathbb{F}_{p^n}$ requires $\mathrm{ACC}(p)$ circuits of exponential size (in $n$), for any fixed prime $p > 2$. Similar bounds hold for quadratic residuosity. As a corollary, we obtain non-trivial bounds for exponential sums that express the correlation between the quadratic character of $\mathbb{F}_{p^n}$ and $n$-variate polynomials over $\mathbb{F}_p$ of degree up to $n^{\epsilon}$ for some $0 < \epsilon < 1$.

• The article: PDF (284 KB)
• Source material: ZIP (84 KB)