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

提起姚期智,大部分人的第一反应会想到图灵奖。如今作为国内第一名也是唯一一名图灵奖获得者,姚期智自 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 条评论
登录 后参与评论

相关文章

来自专栏量子位

清华,就要成为地表最强研究机构了

虽然CS单项排名,北邮排名超过了伯克利,也不要光顾着嘲讽,就忘了这张榜上,清华才是第一。

1052
来自专栏VRPinea

AR教科书陆续出版,或可解决传统书籍部分痛点

最近,被誉为“蓝色生死恋进阶版”的第九版医学人卫教材,因为加入AR而火了。小编一面感叹我朝的教材“腰间盘”咋这么突出勒!一面惋惜自己的“生不逢时”。

1592
来自专栏云计算D1net

惠普分拆将带来5大好处:扩大软件和云计算业务

10月6日,《华尔街日报》报道称,惠普计划分拆为两家公司,最早将于当地时间周一公布分拆计划。尽管并不让人感到意外,但惠普此时分拆引发了“为什么是现在?”的问题。...

3005
来自专栏大数据文摘

快讯丨斯坦福等高校联合研发的律政界AlphaGo,刚刚战胜了20名顶级律师

1538
来自专栏VRPinea

化身为鹰的我,在VR中如同一条死狗

3256
来自专栏量子位

第八冠!清华的三大超算竞赛总冠军奖杯又多了一个

安妮 问耕 发自 凹非寺 量子位 报道 | 公众号 QbitAI ? 又是一场激战。清华又赢了。 刚刚落幕的2017国际超算大会(ISC17)期间,清华大学摘得...

3114
来自专栏VRPinea

别让祖国的花朵,被蓝鲸杀死

3086
来自专栏新智元

英特尔今天50岁,一文看尽芯片50年发展史

【新智元导读】7月18日,英特尔迎来了它50周岁的生日。这位CPU巨头50年来曾带来PC市场的辉煌,如同PC时代的催化剂,只要有计算的地方就有他的身影;他也曾一...

563
来自专栏大数据和云计算技术

政务大数据系列7:政务大数据的部署结构

政务是个大市场,阿里、腾讯、电信、华为都在赔本赚吆喝。本文作者宇同学是资深从业人士,研发总监,他会写一系列文章来阐述政务云全景。 前面六篇...

45711
来自专栏VRPinea

3.6 VR扫描:以色列MR创企完成75万美元融资;哈佛大学研发模拟人眼的变焦镜片

2706

扫码关注云+社区