姚期智到底有多牛？細數中國唯一圖靈獎得主在三大領域的學術造詣

　　本文作者：奕欣

　　2017-02-23 10:25

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

　　提起姚期智，大部分人的第一反應會想到圖靈獎。如今作為國內第一名也是唯一一名圖靈獎獲得者，姚期智自 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 年的科研歷程中所潛心鑽研的。

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