#

### Volume 2016

#### Article 10

Published by the Department of Computer Science, The University of Chicago.

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

Arkadev Chattopadhyay

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)
**BibTeX** entry for this
article (324 bytes)

Submitted November 10, 2014, revised March 28, 2016, and in final form July 28, 2016, published August 3, 2016.

Volume 2016, Article 9
Article 11

Volume 2016
Published articles