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

姚期智這個名字總與「圖靈獎」掛鉤，而如果你了解他的學術(shù)造詣，也會知道這一獎項也是實至名歸。

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

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

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

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

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

在 1978 年，姚期智對數(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)建算法的下限證明。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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