期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2016
卷号：2016
页码：1-16
DOI：10.4086/cjtcs.2016.010
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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$
