学界 | 姚期智到底有多牛?细数中国唯一图灵奖得主在三大领域的学术造诣

提起姚期智,大部分人的第一反应会想到图灵奖。如今作为国内第一名也是唯一一名图灵奖获得者,姚期智自 2011 年起担任清华交叉信息研究院院长,为培养国内优秀人才做出了巨大贡献。今天,AI科技评论就和大家一起细数姚期智院士的学术造诣,「数风流人物,还看今朝」。

姚期智这个名字总与「图灵奖」挂钩,而如果你了解他的学术造诣,也会知道这一奖项也是实至名归。

生于上海,迁居香港,又移民台湾,姚期智在台湾大学完成了物理学学士学位后,赴哈佛大学就读物理学硕士及博士,师从 1979 年诺贝尔物理学获得者 Sheldon Glashow。随后,他只花了两年时间就拿下了伊利诺伊大学的计算机科学博士学位,师从刘炯朗。

自1975年毕业之后,姚期智分别在 MIT、斯坦福、加州大学伯克利分校等世界顶级名校从事教学及研究。他的主要贡献主要包括了三大领域,也大致可以分为三大阶段:

第一阶段:算法理论创新

早在博士就读期间,姚期智提出了随机化算法复杂度的论证,而如今已经成为研究者无人不知的重要工具。

在 1977 年的论文中,姚期智提出了 Yao's min-max principle,这一原理成为了推理随即算法与复杂度的基本技术,也已经应用于属性测试与学习理论等领域。

在 1978 年,姚期智对数据结构的创新做出了根本性的创新。在《Should tables be sorted?》论文中,他介绍了一种名为 cell-probe model 的数据结构抽象模型,目前已经被广泛应用于创建算法的下限证明。

在这一阶段,姚期智最重要的贡献在于提出了理论计算机科学的重要次领域:通讯复杂性和伪随机数生成计算理论。

第二阶段:奠定密码学基础

1982 年,姚期智从加州大学伯克利分校的计算机科学系重回斯坦福大学任教,研究的重心从原来的算法理论逐渐转移到密码学、计算机安全及随机计算领域。而其中最为出名的一个问题,当数姚氏百万富翁问题。这到底是何方难题,且听雷锋网 AI 科技评论道来。

话说西晋时期,石崇与王恺争豪。压倒王恺的最后一根稻草,不是「并穷绮丽,以饰舆服」,而是他视若珍宝的二尺珊瑚树却被石崇用铁如意击碎,更碾压的是,石崇还拿出了「条干绝世」的珊瑚树,让王恺惘然自失。

一叶知秋,只从小小的珊瑚树,就可一窥双方家底深浅。然而如果难度再升一级,连珊瑚树也不让比,土豪们要如何炫富才能不着痕迹地一比高下?

而在千年之后的 20 世纪,姚期智也以「比壕」为主题,提出了驰名的「姚氏百万富翁问题」:两个百万富翁如何在不向对方透露任何身家信息的前提下比较各自的财富?

这一问题后来也衍生为安全多方计算问题的起源:如何在一个互不新任的多用户系统中,各用户能通过网络协同完成计算任务,但又能保证各自数据的安全性?

安全多方计算问题一经提出,吸引了不少学者研究,后来也成为了密码学协议研究的基础问题之一,目前已经被广泛应用于解决数据挖掘、数据库查询、科学计算等许多计算领域的问题。而姚期智自然也成为了现代密码学基础的奠基人。在 1982 年,姚期智给出了一种解决方案:通过生成随机数,加上公开密钥与私有密钥的加密再进行比较,避免了实数域的有序性和加减的可逆性带来多余信息的暴露。

而除了姚氏百万富翁问题外,姚期智在加密和安全计算方面也做出了开创性的贡献,「Dolev-Yao 模型」已经成为了大多数符号安全工作的起点,而《陷门函数的理论和应用》(Theory and applications of trapdoor functions)及《安全计算的协议》(Protocols for secure computations)等著作也成为了安全计算领域的重要著作。此外,还有去随机化领域的基本技术 XOR-lemma 及解决安全多方计算的乱码电路技术,也同样由姚期智提出。

第三阶段:量子计算领域

在 20 世纪 90 年代后,在普林斯顿大学 William and Edna Macaleer 工程与应用科学任教期间,姚期智开始着手开展量子计算、通信及信息理论方面的工作。在 1993 年的论文《Quantum circuit complexity》中,姚期智就将通信封复杂度扩展到量子计算领域,完成了量子计算机的理论基础。在线路复杂性、计算几何、数据结构及量子计算领域,姚教授提出了不少开放性问题,并开拓了不少富有建设性的创见。

在 1995 年,姚期智提出了分布式量子计算模式,后来成为了分布式量子算法和量子通讯协议安全性的基础。

凭借姚期智在计算理论的基本贡献,包括基于复杂性的伪随机数生成,密码学和通信复杂性的理论,美国计算机协会 ACM 于 2000 年授予其图灵奖及百万美元奖金,以表彰姚期智在计算机界做出的巨大贡献。

著作等身,名利双收,如果一直在美国高校继续教书育人,完善理论创新,姚期智诚然会是众多华人学者中最为顶尖的一个,这样的人生轨迹也算得上圆满。但他在 57 岁时做出了一个决定:回到中国担任清华教授。

「落叶归根」,助力算法理论及交叉学科发展

在 2004 年,姚期智回国担任清华大学高等研究中心教授,原本计划的是构建培养博士生的机制,并打造一支研究团队。但随即姚教授意识到,国内传统比较重视计算机工程方面的学习,而为了更好地提升学生的国际视野,姚期智开设了国内首门计算机理论课程,从根本上夯实了计算机本科课程的理论基础。

隔年,姚期智开设了鼎鼎有名的「姚班」,桃李满天下。旷视科技三巨头、中国大学生计算机编程第一人「楼教主」、邹昊等人都是「姚班」的得意门生,具体介绍可查看 AI 科技评论撰写的《中国唯一的图灵奖获得者姚期智,在清华开设的「姚班」有哪些 AI 名徒?》。

据不完全统计,仅截至 2014 年,计算机科学实验班学生本科期间共发表论文 110 篇,其中以学生为论文通讯作者或主要完成人的共 84 篇,有些文章甚至达到了博士毕业的水准。而截至 2016 年 12 月,姚班学生为论文通讯作者或主要完成人的已发表论文达 121 篇,并有 42 位优秀姚班学生被选派参加国际会议并作论文宣讲。

2010 年 12 月,姚期智牵头成立清华大学交叉信息研究院并担任院长,这是全国首个针对计算机科学与技术和物理学两大学科方向的交叉建设学院,而这两个领域正是姚期智在过去 20 年的科研历程中所潜心钻研的。

如果一定要总结姚教授回国后的最大贡献,非百年树人莫属。不论是丰富了算法理论的研究多样性,或是带动了计算机科学与物理学之间的联系,姚教授对国内顶尖学术人才的培育功不可没。而近日雷锋网也曾报道姚期智已放弃外国国籍,从中国科学院外籍院士转为中国科学院院士,这一消息也坐实了姚教授将继续留在国内继续科研及教育事业的想法,相信在未来,会有更多的姚班学生在工业界与学术界发光发热。

原文发布于微信公众号 - AI科技评论(aitechtalk)

原文发表时间:2017-02-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习自然语言处理

如何不出国门走进NLP学术前沿

导读 众所周知,参加学术会议是进入学术圈、走进学术前沿的重要方式。在学术会议上,不仅可以集中听取最新的成果报告,还有讲习班、工作坊、社交活动等形式,了解那些不...

4598
来自专栏腾讯高校合作

治学六字箴言:基础、视野、坚持 ——犀牛鸟之夜@斯德哥尔摩

1092
来自专栏机器之心

清华大学成立AI研究院:张钹院士任院长,Jeff Dean成为计算机学科顾问

在上午的发布会上,清华大学表示,新成立的研究院将致力于以人工智能理论和基础方法研究为核心,积极推进大跨度学科交叉融合,积极推进大范围技术与产业、学校与企业的融合...

951
来自专栏量子位

SQuAD2.0来了!新增5万人工撰写问题,且不一定有答案 | ACL最佳短论文

今日(6月13日),斯坦福NLP团队对外宣称,机器阅读理解数据集SQuAD(Stanford Question Answering Dataset)完成新一波更...

693
来自专栏AI科技评论

大会 | 第七届全国社会媒体处理大会三项技术评测开始报名了

全国社会媒体处理大会(SMP)由中国中文信息学会社会媒体处理专委会主办,专注于以社会媒体处理为主题的科学研究与工程开发,为传播社会媒体处理最新的学术研究与技术成...

722
来自专栏PPV课数据科学社区

缅怀 | 中国人工智能先驱、国家最高科技奖得主吴文俊逝世

一个悲伤的消息:首届国家最高科技奖获得者、著名数学家吴文俊院士因病5月7日在北京去世。 中国科学院数学与系统科学研究院今天发布讣告称,首届国家最高科技奖获得者、...

2617
来自专栏专知

【学术盛宴 】多媒体顶级会议ACM Multimedia 2017 China Pre-conference论文宣讲研讨会

【导读】第25届ACM国际多媒体会议(ACM International Conference on Multimedia, 简称ACMMM)于2017年10月...

28712
来自专栏腾讯高校合作

『抢票结果揭晓!』CCF《社交网络与数据挖掘-学科前沿讲习班》

中国计算机学会《社交网络与数据挖掘-学科前沿讲习班》价值1725元门票免费派送(仅2张!) 关注腾讯高校合作独享福利 讲习班时间:2014年8月10-12日 地...

2734
来自专栏AI科技评论

会议 | CCF NLPCC 2018 自然语言处理与中文计算国际会议

NLPCC 将在 2018 年 8 月 26 日-30 日于内蒙古呼和浩特举行。 ? CCF 自然语言处理与中文计算国际会议 (NLPCC) 是由中国计算机学会...

3935
来自专栏AI科技大本营的专栏

2017清华本科生特等奖得主出炉,AI学霸乔明达获奖

说到学霸,今天偶然瞥见一条新闻,“清华”、“本科生”、“特等奖”……这是什么东东?虽然抱着内心会受到一万点伤害的危险,营长还是果断地点开了链接…… ? 这是从“...

4019

扫描关注云+社区