## Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields

**Title:** Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields

**Speaker**：Qi Cheng（University of Oklahoma）

**Date:** 15:00-16:00pm, December27, 2013

**Place: **Conference Room A404, Department of Mathematical Sciences

**Abstract:** We present a deterministic $2^{O(t)}q^{\frac{t-2}{t-1}+o(1)}$ algorithm to decide whether a univariate polynomial f, with exactly t monomial terms and degree < q，has a root in $\F_q$. Our method is the first with complexity {\em sub-linear} in q when t is fixed. We also prove a structural property for the nonzero roots in $\F_q$ of any t-nomial: the nonzero roots always admit a partition into no more than $2\sqrt{t-1}(q-1)^{\frac{t-2}{t-1}}$ cosets of two subgroups $S_1 \subseteq S_2$ of $\F^*_q$. This can be thought of as a finite field analogue of Descartes' Rule.

When t is not fixed we show that, for p prime, detecting roots in $\F_p$ for f is NP-hard with respect to BPP-reductions. Finally, we prove that if the complexity of root detection is sub-linear (in a refined sense), relative to the straight-line program encoding, then $NEXP \not\subseteq P/poly$.

**Profile of speaker**：Dr. Qi Cheng is an associate professor in the School of Computer Science at the University of Oklahoma, where he joined in 2001. He received his B.Sc degree from Nankai University in 1992, M.Sc. degree from Fudan University in 1995, and PhD degree from University of Southern California in 2001.

His research interests are in the areas of theoretical computer science, cryptography and computational number theory.

**Contact**：Mei Lu