题 目：Algebraic input Models to Np-Complete Problems

主讲人：万大庆

时 间：2024年9月11日16:00

地 点：长大国际公寓三楼会议室

主办单位：理学院

主讲人简介：

万大庆，美国加州大学尔湾分校教授，于1991年博士毕业于华盛顿大学，导师为N. Koblitz教授。后在内华达大学和宾夕法尼亚州立大学任教六年，于1997年到美国加州大学尔湾分校任副教授，2001年起任教授。万教授被评为教育部海外杰出青年，获得世界华人数学家大会晨兴数学银奖。

万大庆教授的研究方向是数论和算术代数几何，尤其是有限域上的zeta函数和L-函数，解决了现代数论中的若干著名猜想，包括Dwork猜想，Katz猜想，Adolphson-Sperber猜想等。已在《Annals of Mathematic》，《Invent. Math.》，《J. Amer. Math. Soc.》上发表文章7篇，其研究工作在算术代数几何的许多重要领域产生了影响。近年来，万教授在计算数论、编码和计算复杂性领域也做出了许多杰出的工作，其结果发表在FOCS、STOC、FOCM、J. of Complexity、IEEE IT等计算机和信息理论的重要会议和杂志上。现为国际著名数学杂志《Journal of Number Theory》和《Finite Fields and Their Applications》编委。

摘要：

The most important problem in theoretical computer science is the P vs NP problem, which says that any NP-complete problem cannot be solved in polynomial time. This, however,depends on the range of the input parameters. In the first part, we illustrate this with the usual dense input model for the subset sum problem.In the second part, we introduce an algebraic input model which makes the problem even harder, and yet one can prove that there is a polynomial time algorithm for a much larger range of input parameters. The proof depends crucially on a good estimate of exponential sums over the image set of a polynomial map, which in turn depends on the Weil conjectures.