提起姚期智，大部分人的第一反應(yīng)會(huì)想到圖靈獎(jiǎng)。如今作為國(guó)內(nèi)第一名也是唯一一名圖靈獎(jiǎng)獲得者，姚期智自 2011 年起擔(dān)任清華交叉信息研究院院長(zhǎng)，為培養(yǎng)國(guó)內(nèi)優(yōu)秀人才做出了巨大貢獻(xiàn)。今天，雷鋒網(wǎng)AI科技評(píng)論就和大家一起細(xì)數(shù)姚期智院士的學(xué)術(shù)造詣，「數(shù)風(fēng)流人物，還看今朝」。

姚期智這個(gè)名字總與「圖靈獎(jiǎng)」掛鉤，而如果你了解他的學(xué)術(shù)造詣，也會(huì)知道這一獎(jiǎng)項(xiàng)也是實(shí)至名歸。

生于上海，遷居香港，又移民臺(tái)灣，姚期智在臺(tái)灣大學(xué)完成了物理學(xué)學(xué)士學(xué)位后，赴哈佛大學(xué)就讀物理學(xué)碩士及博士，師從 1979 年諾貝爾物理學(xué)獲得者 Sheldon Glashow。隨后，他只花了兩年時(shí)間就拿下了伊利諾伊大學(xué)的計(jì)算機(jī)科學(xué)博士學(xué)位，師從劉炯朗。

自1975年畢業(yè)之后，姚期智分別在 MIT、斯坦福、加州大學(xué)伯克利分校等世界頂級(jí)名校從事教學(xué)及研究。他的主要貢獻(xiàn)主要包括了三大領(lǐng)域，也大致可以分為三大階段：

第一階段：算法理論創(chuàng)新

早在博士就讀期間，姚期智提出了隨機(jī)化算法復(fù)雜度的論證，而如今已經(jīng)成為研究者無(wú)人不知的重要工具。

在 1977 年的論文中，姚期智提出了 Yao's min-max principle，這一原理成為了推理隨即算法與復(fù)雜度的基本技術(shù)，也已經(jīng)應(yīng)用于屬性測(cè)試與學(xué)習(xí)理論等領(lǐng)域。

在 1978 年，姚期智對(duì)數(shù)據(jù)結(jié)構(gòu)的創(chuàng)新做出了根本性的創(chuàng)新。在《Should tables be sorted?》論文中，他介紹了一種名為 cell-probe model 的數(shù)據(jù)結(jié)構(gòu)抽象模型，目前已經(jīng)被廣泛應(yīng)用于創(chuàng)建算法的下限證明。

在這一階段，姚期智最重要的貢獻(xiàn)在于提出了理論計(jì)算機(jī)科學(xué)的重要次領(lǐng)域：通訊復(fù)雜性和偽隨機(jī)數(shù)生成計(jì)算理論。

第二階段：奠定密碼學(xué)基礎(chǔ)

1982 年，姚期智從加州大學(xué)伯克利分校的計(jì)算機(jī)科學(xué)系重回斯坦福大學(xué)任教，研究的重心從原來(lái)的算法理論逐漸轉(zhuǎn)移到密碼學(xué)、計(jì)算機(jī)安全及隨機(jī)計(jì)算領(lǐng)域。而其中最為出名的一個(gè)問(wèn)題，當(dāng)數(shù)姚氏百萬(wàn)富翁問(wèn)題。這到底是何方難題，且聽(tīng)雷鋒網(wǎng) AI 科技評(píng)論道來(lái)。

話說(shuō)西晉時(shí)期，石崇與王愷爭(zhēng)豪。壓倒王愷的最后一根稻草，不是「并窮綺麗，以飾輿服」，而是他視若珍寶的二尺珊瑚樹(shù)卻被石崇用鐵如意擊碎，更碾壓的是，石崇還拿出了「條干絕世」的珊瑚樹(shù)，讓王愷惘然自失。

一葉知秋，只從小小的珊瑚樹(shù)，就可一窺雙方家底深淺。然而如果難度再升一級(jí)，連珊瑚樹(shù)也不讓比，土豪們要如何炫富才能不著痕跡地一比高下？

而在千年之后的 20 世紀(jì)，姚期智也以「比壕」為主題，提出了馳名的「姚氏百萬(wàn)富翁問(wèn)題」：兩個(gè)百萬(wàn)富翁如何在不向?qū)Ψ酵嘎度魏紊砑倚畔⒌那疤嵯卤容^各自的財(cái)富？

這一問(wèn)題后來(lái)也衍生為安全多方計(jì)算問(wèn)題的起源：如何在一個(gè)互不新任的多用戶系統(tǒng)中，各用戶能通過(guò)網(wǎng)絡(luò)協(xié)同完成計(jì)算任務(wù)，但又能保證各自數(shù)據(jù)的安全性？

安全多方計(jì)算問(wèn)題一經(jīng)提出，吸引了不少學(xué)者研究，后來(lái)也成為了密碼學(xué)協(xié)議研究的基礎(chǔ)問(wèn)題之一，目前已經(jīng)被廣泛應(yīng)用于解決數(shù)據(jù)挖掘、數(shù)據(jù)庫(kù)查詢、科學(xué)計(jì)算等許多計(jì)算領(lǐng)域的問(wèn)題。而姚期智自然也成為了現(xiàn)代密碼學(xué)基礎(chǔ)的奠基人。在 1982 年，姚期智給出了一種解決方案：通過(guò)生成隨機(jī)數(shù)，加上公開(kāi)密鑰與私有密鑰的加密再進(jìn)行比較，避免了實(shí)數(shù)域的有序性和加減的可逆性帶來(lái)多余信息的暴露。

而除了姚氏百萬(wàn)富翁問(wèn)題外，姚期智在加密和安全計(jì)算方面也做出了開(kāi)創(chuàng)性的貢獻(xiàn)，「Dolev-Yao 模型」已經(jīng)成為了大多數(shù)符號(hào)安全工作的起點(diǎn)，而《陷門函數(shù)的理論和應(yīng)用》（Theory and applications of trapdoor functions）及《安全計(jì)算的協(xié)議》（Protocols for secure computations）等著作也成為了安全計(jì)算領(lǐng)域的重要著作。此外，還有去隨機(jī)化領(lǐng)域的基本技術(shù) XOR-lemma 及解決安全多方計(jì)算的亂碼電路技術(shù)，也同樣由姚期智提出。

第三階段：量子計(jì)算領(lǐng)域

在 20 世紀(jì) 90 年代后，在普林斯頓大學(xué) William and Edna Macaleer 工程與應(yīng)用科學(xué)任教期間，姚期智開(kāi)始著手開(kāi)展量子計(jì)算、通信及信息理論方面的工作。在 1993 年的論文《Quantum circuit complexity》中，姚期智就將通信封復(fù)雜度擴(kuò)展到量子計(jì)算領(lǐng)域，完成了量子計(jì)算機(jī)的理論基礎(chǔ)。在線路復(fù)雜性、計(jì)算幾何、數(shù)據(jù)結(jié)構(gòu)及量子計(jì)算領(lǐng)域，姚教授提出了不少開(kāi)放性問(wèn)題，并開(kāi)拓了不少富有建設(shè)性的創(chuàng)見(jiàn)。

在 1995 年，姚期智提出了分布式量子計(jì)算模式，后來(lái)成為了分布式量子算法和量子通訊協(xié)議安全性的基礎(chǔ)。

憑借姚期智在計(jì)算理論的基本貢獻(xiàn)，包括基于復(fù)雜性的偽隨機(jī)數(shù)生成，密碼學(xué)和通信復(fù)雜性的理論，美國(guó)計(jì)算機(jī)協(xié)會(huì) ACM 于 2000 年授予其圖靈獎(jiǎng)及百萬(wàn)美元獎(jiǎng)金，以表彰姚期智在計(jì)算機(jī)界做出的巨大貢獻(xiàn)。

著作等身，名利雙收，如果一直在美國(guó)高校繼續(xù)教書(shū)育人，完善理論創(chuàng)新，姚期智誠(chéng)然會(huì)是眾多華人學(xué)者中最為頂尖的一個(gè)，這樣的人生軌跡也算得上圓滿。但他在 57 歲時(shí)做出了一個(gè)決定：回到中國(guó)擔(dān)任清華教授。

「落葉歸根」，助力算法理論及交叉學(xué)科發(fā)展

在 2004 年，姚期智回國(guó)擔(dān)任清華大學(xué)高等研究中心教授，原本計(jì)劃的是構(gòu)建培養(yǎng)博士生的機(jī)制，并打造一支研究團(tuán)隊(duì)。但隨即姚教授意識(shí)到，國(guó)內(nèi)傳統(tǒng)比較重視計(jì)算機(jī)工程方面的學(xué)習(xí)，而為了更好地提升學(xué)生的國(guó)際視野，姚期智開(kāi)設(shè)了國(guó)內(nèi)首門計(jì)算機(jī)理論課程，從根本上夯實(shí)了計(jì)算機(jī)本科課程的理論基礎(chǔ)。

隔年，姚期智開(kāi)設(shè)了鼎鼎有名的「姚班」，桃李滿天下。曠視科技三巨頭、中國(guó)大學(xué)生計(jì)算機(jī)編程第一人「樓教主」、鄒昊等人都是「姚班」的得意門生，具體介紹可查看 AI 科技評(píng)論撰寫(xiě)的《中國(guó)唯一的圖靈獎(jiǎng)獲得者姚期智，在清華開(kāi)設(shè)的「姚班」有哪些 AI 名徒？》。

據(jù)不完全統(tǒng)計(jì)，僅截至 2014 年，計(jì)算機(jī)科學(xué)實(shí)驗(yàn)班學(xué)生本科期間共發(fā)表論文 110 篇，其中以學(xué)生為論文通訊作者或主要完成人的共 84 篇，有些文章甚至達(dá)到了博士畢業(yè)的水準(zhǔn)。而截至 2016 年 12 月，姚班學(xué)生為論文通訊作者或主要完成人的已發(fā)表論文達(dá) 121 篇，并有 42 位優(yōu)秀姚班學(xué)生被選派參加國(guó)際會(huì)議并作論文宣講。

2010 年 12 月，姚期智牽頭成立清華大學(xué)交叉信息研究院并擔(dān)任院長(zhǎng)，這是全國(guó)首個(gè)針對(duì)計(jì)算機(jī)科學(xué)與技術(shù)和物理學(xué)兩大學(xué)科方向的交叉建設(shè)學(xué)院，而這兩個(gè)領(lǐng)域正是姚期智在過(guò)去 20 年的科研歷程中所潛心鉆研的。

如果一定要總結(jié)姚教授回國(guó)后的最大貢獻(xiàn)，非百年樹(shù)人莫屬。不論是豐富了算法理論的研究多樣性，或是帶動(dòng)了計(jì)算機(jī)科學(xué)與物理學(xué)之間的聯(lián)系，姚教授對(duì)國(guó)內(nèi)頂尖學(xué)術(shù)人才的培育功不可沒(méi)。而近日雷鋒網(wǎng)也曾報(bào)道姚期智已放棄外國(guó)國(guó)籍，從中國(guó)科學(xué)院外籍院士轉(zhuǎn)為中國(guó)科學(xué)院院士，這一消息也坐實(shí)了姚教授將繼續(xù)留在國(guó)內(nèi)繼續(xù)科研及教育事業(yè)的想法，相信在未來(lái)，會(huì)有更多的姚班學(xué)生在工業(yè)界與學(xué)術(shù)界發(fā)光發(fā)熱。

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見(jiàn)轉(zhuǎn)載須知。