报告题目：Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields

报告人：程歧副教授（University of Oklahoma）

时间：2013年12月27日(星期五)15:00-16:00

地点：理科楼数学系A404

摘要：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，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$.

报告人简介：Dr. Qi Cheng is an associate professor in theSchoolofComputer Scienceat theUniversityofOklahoma, where he joined in 2001. He received his B.Sc degree fromNankaiUniversityin 1992, M.Sc. degree fromFudanUniversityin 1995, and PhD degree fromUniversityofSouthern Californiain 2001.

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

联系人:陆玫