蔡进一

威斯康辛大学麦迪逊分校计算机科学系教授

蔡进一教授是国际杰出的理论计算机科学家，他在计数问题的复杂性分类中做了大量的工作并形成系统，证明了图同态的所有复数配分函数的二分定理。他长期关心和支持中国理论计算机科研和教育的发展，积极参与和组织在中国的理论计算机会议。

为此，CCF奖励委员会决定授予蔡进一教授2022年“CCF海外科技人物奖”。

附：贡献简介：

蔡进一教授是国际杰出的理论计算机科学家，ACM、AAAS Fellow。他长期从事计算复杂性理论研究。他在计数问题的复杂性分类中做了大量的工作并形成体系，他的很多二分定理在一个很广的框架中把所有问题分为两类：或者可以在多项式时间内计算（复杂类P），或者等价于#P类中最困难的问题（#P是NP的计数类）。他带领团队对全息算法做了深入全面的阐述，为以后的分类定理奠定了基础。后又证明了图同态的所有复数配分函数的二分定理，“给所有计数问题分类”计划达到了高潮。这些计数问题及配分函数的计算在人工智能、机器学习、数据库和统计物理中有广泛应用。蔡进一教授还有很多其他著名的结果，包括电路复杂性、图同构、交互证明系统、Hartmanis猜想的解決、格问题、Karp-Lipton定理最强形式、和积式与行列式问题等。

蔡进一教授也是年轻计算机科学家、特别是中国年轻计算机科学家的优秀导师。他长期致力于指导、教育年轻的中国学生和研究人员并与他们合作科研，使来自中国的理论计算机领域的研究人员在国际上变得越来越引人注目。

蔡进一教授还积极参与和组织在中国的理论计算机会议，对创办COCOON和TAMC作出了重要贡献。