Loading… 重磅!2021年“哥德尔奖”出炉,两名华人学者斩获理论计算机最高荣誉_TOM商业
正文
Qzone
微博
微信

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

2021-05-13 11:53 前瞻网   

 

近日,理论计算机最高荣誉——“哥德尔奖”公布。今年,一共有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》的两位作者,均是华人学者。

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

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模型等等。

本文来源前瞻网,转载请注明来源。本文内容仅代表作者个人观点,本站只提供参考并不构成任何投资及应用建议。(若存在内容、版权或其它问题,请联系:service@qianzhan.com)

 

责任编辑: 3976DBC

责任编辑: 3976DBC