## 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

SpeakerQi ChengUniversity 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 < qhas 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 speakerDr. 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.

ContactMei Lu