数学科学系

Department of Mathematical Sciences

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

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

 

报告人:程歧副教授(University of Oklahoma

 

时间:20131227(星期五)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 < 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$.

 

报告人简介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.

 

联系人: 陆玫