当前位置:首页 > 商业 > 产经 > 正文

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

2021-05-13 05:44

  近日,理论计算机最高荣誉——“哥德尔奖”公布。今年,一共有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 Gdel,以表彰他对数学逻辑的重大贡献和他的研究兴趣。他在1931年提出了哥德尔不完备性定理。

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

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

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

标签