重磅！2021年“哥德尔奖”出炉，两名华人学者斩获理论计算机最高荣誉

近日，理论计算机最高荣誉——“哥德尔奖”公布。今年，一共有3篇论文共同获得了哥德尔奖：

- The Complexity of the Counting Constraint Satisfaction Problem（作者为Andrei Bulatov）

- An Effective Dichotomy for the Counting Constraint Satisfaction Problem（一作为Martin E. Dyer，二作为David Richerby）

- Complexity of Counting CSP with Complex Weights（作者Jin-Yi Cai、Xi Chen）

其中，获奖论文《Complexity of Counting CSP with Complex Weights》的两位作者，均是华人学者。

Jin-Yi Cai主要从事计算复杂性理论研究。他是复旦大学1977级学生，曾在耶鲁大学(1986-1989)、普林斯顿大学(1989-1993)和纽约州立大学布法罗分校(1993-2000)担任教员，目前是斯坦福大学计算机科学系教授。曾斩获斯隆计算机科学奖学金、古根海姆奖，是《计算机与系统科学杂志》（JCSS）等很多期刊杂志主编。他还被选为了美国计算机协会和美国科学促进会的会员。

而Xi Chen研究兴趣则包括算法博弈论/经济学、复杂性理论。其曾于清华大学获得物理/数学理学学士学位和计算机科学博士学位。师从张钹院士，是姚期智教授领导的计算机理论研究所的成员之一。相关研究曾获得过NSF CAREER奖、斯隆研究奖学金，以及EATCS Presburger奖。

以上三篇论文，均涉及约束满足问题（Constraint Satisfaction Problems，简称CSP)的研究。

“哥德尔奖”的杰出论文奖由EATCS和ACM SIGACT联合赞助。该奖项是为了纪念Kurt Gödel，以表彰他对数学逻辑的重大贡献和他的研究兴趣。他在1931年提出了哥德尔不完备性定理。

该奖项包括5000美元奖金。每年颁发一次，轮流在国际自动机、语言和编程研讨会(ICALP)和ACM计算理论研讨会(STOC)上发表。它将在今年的STOC上展示。

约束满足是计算机科学中一个重要的课题。是对CSP计算复杂度分类的大量工作的成果，并证明了一个用于计算可表示为配分函数的CSP类型问题的全面复杂性二分定理。

这种二分法的最终形式所分类的问题类别是非常广泛的。它包括所有计数CSP，所有类型的图同态(无向或有向，无加权或加权)，以及自旋系统(以及统计物理学中的各种问题)。例子包括计数顶点覆盖，独立集，反链，图着色，Ising模型，Potts模型，q-type Beach模型等等。

参考来源：https://eatcs.org/index.php/component/content/article/1-news/2885-2021-05-07-21-20-13

https://simons.berkeley.edu/people/jin-yi-cai

http://www.cs.columbia.edu/~xichen/Homepage/Welcome.html