报告人：万大庆（美国加州大学）

时间：2024年01月16日 10:00-

地址：理科楼LA103

摘要：The most important problem in theoretical computer science is the P vis 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 polynomial map, which in turn depends on the Weil conjectures.

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

邀请人：孔德荣

欢迎广大师生积极参与！