美国当地时间6月15日晚,计算机理论学界最高奖哥德尔奖(Gödel Prize)颁奖典礼在位于俄勒冈召开的ACM计算机理论研讨会上举行,华人科学家、南加州大学计算机科学Seeley G. Mudd教授滕尚华再次领奖,这也是他与耶鲁大学教授Dan Spielman合作取得的第二个哥德尔奖。此前,他们两人合作的论文曾在2008年获得过一次哥德尔奖。
此次获奖是因为他们在近线性时间拉普拉斯求解器方面发表的一系列论文。当今,社交媒体和手持设备时代的成熟相继催生了大量错综复杂的问题,技术使用者们每天都在生成海量的数据,他们需要迅速高效地进行导航、筛选,这一现实便是驱动滕尚华和Spielman两人研究工作的核心所在。
滕尚华在接受南加州大学学生报纸Daily Trojan采访时说:“我们需要寻求更迅捷的算法,因为大家不可能在Google搜索、社交媒体和移动设备搜索上花老半天时间干等着。线性时间是现代数据库的评测基准。”搜索和整理算法的效率是当今计算处理的关键,滕尚华和Spielman就此探索,共同开发出了强大的算法。在拥有同等计算能力的条件下,他们的算法在面对复杂搜索问题时能产生更快的反应结果。
滕尚华强调说:“早在做博士研究期间我就对图形算法萌发了浓厚的兴趣,不仅仅是考虑到它对于解决当今许多计算问题至关重要,同时也由于它本质上是一门交叉学科。”在一篇回忆任职于微软亚洲研究院时的工作经历的文章中,浙江大学计算机学院教授周昆评价说,滕尚华虽然是一个计算机理论科学家,但他对应用领域的很多问题有着浓厚的研究兴趣。滕尚华曾供职于IBM和英特尔等大型企业。
在NASA工作期间,他甚至协助开发了一项前沿计算软件,使用有限元技术来仿真空气动力模型。对于与他共同获奖的搭档Spielman,滕尚华言语中流露出欣赏和默契,称赞对方才智超群。他们深厚的私交从滕尚华攻读博士学位时便已开始,共同的兴趣爱好让他们有机会数次并肩合作。周昆在上述回忆文章中也回顾了滕尚华和Spielman对光滑分析(smoothed analysis)的贡献。
“有一次在闲聊的时候,他和我提到在做研究的过程中直觉很重要,有的时候对一些没有把握的方向需要做出猜想(conjecture)。当时,理论界已经证明单纯形法在最坏情况下具有指数复杂度。按照常理,这样一个高复杂度的算法很难被应用,可是单纯形法却在工业界被广泛应用。滕尚华和他的合作者就猜想,既然实践已经证明了单纯形法的实用性,那么一定存在着某种限定条件,使得单纯形法的复杂度远远低于指数复杂度。
沿着这一思路,他们最终证明了在大量的工业应用中单纯形法只是多项式复杂度。这一研究工作在理论界和工业界都产生了深刻的影响,相对于传统的最坏情况分析(worst case analysis),这一工作开创了光滑分析的先河。
”原微软亚洲研究院副院长、现上海纽约大学终身教授张峥告诉《赛先生》:“计算机科学虽然只有几十年历史,但已经发展成一个特别庞杂的生态系统,有直接插入现实土壤的系统软件和体系结构,也有直入云端,站在象牙塔尖的算法理论。我对做算法的拔尖专家特别膜拜,因为他们每获得一个厉害的成果,就有足以搬动整座塔的坐标的潜力。”在微软亚洲研究院工作的时候,张峥主持过一个大规模矩阵运算的项目,他曾为此专门请教过滕尚华。
“其实去之前我有个假设,就是图计算可以转化为简单的矩阵算子的组合,并没有期待有更多的收获。滕尚华介绍了他们最新的一个结果,却完全出乎我意料。时间长了记不清其中细节,只记得离开的时候很感慨,觉得我们天天习以为常的那些基础,真有分分钟被这帮‘魔鬼科学家’颠覆的可能。”张峥说。
滕尚华,1985年毕业于上海交通大学,获得电气工程和计算机科学双学士学位,尔后相继在南加州大学和卡内基梅隆大学获得硕士和博士学位,曾在麻省理工学院、明尼苏达大学、伊利诺伊大学厄巴纳—香槟分校和波士顿大学任教。滕尚华于2009年当选美国计算机协会会士(ACM fellow),同年获得由美国数学学会和美国数学规划学会颁发的富尔克森奖(Fulkerson Prize)。
哥德尔奖(Gödel Prize)以20世纪科学和哲学事业的奠基人库尔特·哥德尔(Kurt Gödel)的名字命名,由欧洲计算机学会(EATCS)与美国计算机学会基础理论专业组织(ACM SIGACT)于1993年共同设立,是计算机理论领域最高奖,每年颁给计算机理论领域最杰出的学术论文,以表彰科学家在数理逻辑和计算机科学领域做出的杰出贡献。
此前,歌德尔奖的得主中不乏图灵奖得主Silvio Micali、沃尔夫数学奖得主László Lovász等著名科学家。截至目前,滕尚华是唯一一位获得哥德尔奖的华人学者。