姚期智

姚期智

姚期智(Andrew Chi-Chih Yao),世界著名電腦學家,2000年圖靈獎得主,美國科學院院士,美國科學與藝術學院院士,中國科學院外籍院士,清華大學高等研究中心教授,香港中文大學博文講座教授。1967年獲得台灣大學物理學士學位,1972年獲得美國哈佛大學物理博士學位,1975年獲得美國伊利諾依大學電腦科學博士學位。1975年至1986年曾先後在美國麻省理工學院數學系、斯坦福大學電腦系、加利福尼亞大學伯克利分校電腦系任助理教授、教授。2004年起在清華大學任全職教授。2005年出任香港中文大學博文講座教授。

現任清華大學交叉信息研究院院長、教授。

  • 中文名稱
    姚期智
  • 外文名稱
    Andrew Chi-Chih Yao
  • 國籍
    美國
  • 出生地
    上海
  • 出生日期
    1946年12月24日
  • 職業
    電腦學家
  • 畢業院校
    伊利諾依大學
  • 主要成就
    2000年圖靈獎得主
  • 職稱
    教授
  • 工作單位
    清華大學交叉信息研究院

​概述

(圖)姚期智(圖)姚期智

姚期智祖籍湖北孝感,1946年12月24日出生于上海,幼年隨父母移居台灣。1967年,姚期智畢業于台灣大學,之後赴美國深造。1972年獲哈佛大學物理學博士學位,1975年獲伊利諾大學香檳分校(UIUC)電腦科學博士學位。之後,他曾先後在麻省理工學院(1975—1976)、斯坦福大學(1976—1981,1983—1986)、加州大學伯克利分校(1981—1983)等美國高等學府從事教學和研究,1986年至2004年任普林斯頓大學電腦科學系教授,從2004年9月至今任北京清華大學高等研究中心教授。此外,姚期智還是美國國家科學院院士、美國人文及科學院院士、中國科學院外籍院士及台灣中央研究院院士。

多年來,姚期智先生以其敏銳的科學思維,不斷向新的學術領域發起沖擊,在資料組織、基于復雜性的偽亂數生成理論、密碼學、通信復雜性乃至量子通信和計算等多個尖端科研領域,都做出了巨大而獨到的貢獻。他所發表的近百篇學術論文,幾乎覆蓋了計算復雜性的所有方面,並在獲圖靈獎之前,就已經在不同的科研領域屢獲殊榮,曾獲美國工業與套用數學學會喬治·波利亞獎和以演算法設計大師克努特命名的首屆克努特獎,是電腦理論方面國際上最拔尖的學者。

經歷

(圖)姚期智(圖)姚期智

自1975年獲得美國伊利諾伊大學電腦科學博士學位,姚期智在理論電腦領域作研究至今,曾先後在美國麻省理工學院、斯坦福大學、加州大學伯克利分校、普林斯頓大學等著名學府擔任教授,從事教學及研究工作。多年來,姚期智以其敏銳的科學思維,在資料組織、密碼學、通信復雜性乃至量子通信和計算等多個尖端科研領域,都作出了巨大而獨到的貢獻,曾獲美國工業與套用數學學會George Polya獎,美國電腦協會演算法與計算理論分會(ACM SIGACT)Donald E.Knuth獎等榮譽。全球首要電腦協會(ACM)在2000年授予姚期智圖靈獎。姚期智是圖靈獎創立以來首位獲獎的亞裔學者,也是迄今為止獲此殊榮的唯一華裔電腦科學家。圖靈獎是世界電腦科學領域的最高獎項,與物理、化學醫學經濟學領域的諾貝爾獎齊名。

2004年姚期智離開普林斯頓大學,到清華大學任全職教授。

中國情結

(圖)姚期智(圖)姚期智

“我所學的東西能有機會在我出生的中國生根,有條件在該領域為中國培養出世界級的研究人員來,我覺得這是一件非常有意義的事情。”

人生頭20年生活在中國,20歲以後生活在美國,57歲以後又將人生歸宿在中國大陸的姚期智的人生軌跡宛如一個圓。

生在上海,長在台灣,卻在美國接受了36年熏陶的姚期智自己也沒有料到,在中國所接受的教育是如此根深蒂固,尤其是隨著年齡的成長,也許是人生經驗多了的緣故,姚期智對中國文化的感受更加深刻了。

“他是懷有中國情結的。”現任清華高等研究中心主任的聶華桐先生說,“前幾天,我們聊天,他說他在清華教育年輕一代,有一種滿足感,是在美國教美國學生時所沒有的。在這裏,他教育的是中國年輕人!

現在,了解中國的歷史,欣賞中國的文化,聽古典音樂,閱讀專業以外的書籍,依舊是姚期智“閒暇”之餘的主要內容。

“中國是我的祖國,我受中國傳統文化的教育和影響是非常深厚的,我對整個中國的感情非常深厚。目前國內有一個很好的目標,要建設出幾個世界一流的研究型大學來,我覺得我現在能在清華參與這件工作也算是一點小小的貢獻。希望能盡點兒微薄之力。”

奮鬥之路

1967年,姚期智帶著自己的行囊走進了哈佛大學,追隨導師格拉肖(Sheldon Lee Glashow,1979年諾貝爾物理學獎得主),開始了自己的物理世界探索之旅,並順利地拿到了物理學博士學位。1973年,26歲的姚期智做出了一生中的重要決定:放棄苦心鑽研多年的物理學,轉而投向方興未艾的電腦技術。

“就能力和性格而言,我更適合搞電腦。物理看重直覺,你必須推想出問題的正確答案,求證也許不嚴格。可數學,包括電腦,最重要的是你必須用嚴密的數學推理來證明這個答案。我發現自己的論證能力在電腦領域更合適。”

1973年,姚期智進入素以電腦科學研究的深厚積淀而聞名的伊利諾大學攻讀電腦科學博士學位。兩年後,他如願以償。

“做研究的人也是不同的,每個人做事的方式也不一樣。我比較喜歡新奇的東西,有新的方向我就喜歡去看一看,試一試。”

變化迅猛的電腦研究更具有這方面的特徵,使得姚期智津津樂道其中:“我喜歡做這類事情,怎樣把一個東西變成一個問題,然後再去解決它。”

但並不是每一個事情他都去嘗試新的。“比如走路,從A點走到B點,我知道一條路的話,我會總走這條路。我不太喜歡走一條新的路或者短一點的路。吃東西也是一樣的,有哪幾樣東西如果經常吃的話,我就很滿意了。聽音樂,我比較喜歡聽古典音樂,流行音樂我的知識還局限在20年前。”

姚期智姚期智

姚期智說,年輕的時候你可能感到有許多事情可以去嘗試,當你投身到某一個領域以後,你可能就沒有時間花在別的事情上了,而隻能在你所傾心的領域不斷探索和追求。

隨著研究的不斷深入,閱讀成為姚期智緩解壓力的主要手段之一。讓他感到驚喜的是,這種隨便翻一翻的閱讀方式卻對他產生了重要影響。

“年輕的時候我認為我現在做的東西是世界上最重要,別的事情都不值得做。從某種意義上講這也是一件好事,你認為有意義,你才會有那麽大的興趣和那麽大的投入。當你在你的領域研究鑽研得比較深了以後,慢慢地你的視野會比較大一點,你會知道你的研究在世界上充當一個怎樣的角色。你會覺得自己所取得的成就隻是在這個世界上做出了一點小小的貢獻。”

也許正是因為這一點,又引發了姚期智新的探索欲望。

早在1970年末以前,密碼學尚屬政府研究範疇。隨著社會的發展,人們感到密碼學在未來商業行為中會越來越頻繁地使用。怎樣在通信上有一種保密的方法?怎樣用計算理論解決密碼學上的問題?這成為當時誕生的一個新的研究領域。姚期智就從那個時候開始做這方面的研究工作。“我之所以選擇這樣的研究工作,是因為這是比較有影響的工作。這個工作不隻是局限在我們這個領域,別的科學家也會對它產生興趣。”

成功理念

(圖)姚期智(圖)姚期智

重新翻閱人生之路這部大書,細細品味所走過的路,在翻越了許許多多的曲曲折折之後,展現在姚期智眼前的是生命的滄海。然而,那幾乎覆蓋了計算復雜性的所有方面的近百篇學術論文;那些在資料組織、基于復雜性的偽亂數生成理論密碼學、通信復雜性乃至量子通信和計算等多個尖端科研領域做出的巨大而獨到的貢獻;那由于他在計算理論研究方面做出的諸多“根本性的、意義重大的”貢獻而獲得的圖靈獎,以及美國國家科學院院士、美國人文及科學院院士、中國科學院外籍院士等戴在頭上的光環,都不是姚期智理念上的成功。在他看來,成功意味著做出超乎自己能力的事情。

姚期智認為,年輕學子們不要隻把目光局限在自己的學科,應該不斷學習其他事情。“有如此眾多不同的領域的美麗,如果限製欣賞的範圍,那是一種遺憾。”他的導師、諾貝爾物理學獎得主格拉肖曾經告訴姚期智“要大膽、創新”。正是在這種做學問的基本精神的驅使下,使姚期智不斷向新的學術領域發起沖擊。

“成功有很多不同的模式,如果在每一個模式裏你都有自己的想法,做得特別好,那麽都能夠成功。一般來講,學校專業比較完整,如哈佛大學,有各種專業學院,那麽它就能夠辦成世界一流大學。但這也有例外,普林斯頓大學傳統的理念是,他們不需要做所有的事情,他們隻需要把想做的事情都做好,做得最好。這是他們的成功之道。”

普林斯頓大學的成功理念仍然影響著在那裏工作生活了多年的姚期智。他仍然堅守著“還是希望有我自己控製的時間和控製的環境。生命有許多階段,工作有許多性質,在有些階段,幾乎要百分之百地做一件事情。”

性格與成功

姚期智認為性格與一個人的成長“唇齒相依”。

性格上的堅忍不拔是成功的重要因素。姚期智說,遇到困難,人們往往有兩種處理方法,一種是換別的事情幹幹,一種是想辦法克服它。開啟成功寶典,一般情況下要有相當程度忍受失敗的精神,不能一件事情幹一段時間不成功,馬上換一件事情做。“我想,每一件值得做的事情都是要克服某一層面的困難的,一件事情如果別人能做的話,恐怕別人都已經做過了。當然性格上的堅忍不拔也要有個‘度’。要知道什麽時候要堅持,什麽時候要放棄。”

姚期智姚期智

姚期智的工作信條是:如果你有十件失敗,有一件成功這就很好了。“我們搞研究和從事事務性的工作不一樣。從事事務性的工作如果幹十件事情有九件事情幹砸了,就可能沒有工作了。對研究來講,研究過程的不成功是沒有關系的,真正重要的隻是你成功的結果。”

對姚期智來講,挫折感主要是在研究的過程中,碰到的問題更多的是解決問題上。

“最開始不知道做不成功是因為自己太笨,還是因為問題太難。當你一再失敗的時候,你會問自己還會不會做出成功的事情來。過一兩年你會對自己有所了解,有所了解以後會比較容易一點。”

姚期智說,每個人由于性格的不同,選擇問題和處理問題的方法也會不太一樣。他的原則是,在選擇課題的時候,不能選擇超過自己能力太大的課題,不能野心很大,要量力而行。但也不要選擇太容易的問題。最好選擇比你的能力稍稍高一點的問題進行研究,當你的能力得到培養以後,你再選擇更難一點的課題進行研究。

“剛開始我寫很多文章,看到的問題我都想去解決它。後來就比較挑一點,會選擇比較難一點的問題進行研究,寫的文章也會慢慢少一點。因為一開始你要培養你的能力的話,你就要多做一些事情,等能力夠了以後,你才有資格選擇比較重要的事情去做。這種性格有助于增強自己的自信心和挖掘自己的潛能,也容易成功。”

始終在名校執教的姚期智先生不僅堅守著自己的成功理念,而且將其引入育人理念之中。了解他的同事都知道,他帶學生,會先出些題目讓他做做看,看他對問題的興趣和解決問題的能力,了解他的數學根底,看他對自己的指導是否滿意,然後再看怎麽樣是最好的配合。

他認為學生能夠自動、自發,有很強的欲望想要做出東西來的動機是最重要的。學生必須對這方面的問題有真正的興趣。“我們這個領域比較像數學,要有很大的興趣才能做出成就來,像做家庭作業一樣的方式是做不出成就的。”

意外收獲

姚期智姚期智

姚期智的事業之路不能說是一條直線。1967年,當他填寫大學所學專業時,選擇物理學並不是出于真正的對物理學的了解。但是,在以後學習物理的過程中,接觸到了相對論和量子學,了解了其中的意義的時候,那種感覺至今仍然令姚期智記憶猶新:“那是我一生中最快樂的時候。對我們研究科學的人來說,那就是最令人喜悅的事情。”

這個意外收獲,將姚期智帶入到了一個新的境界。物理上的經驗使他知道有另外一個世界,而對文學的喜愛使他學會如何更好地與人溝通,同時幫助他了解了學文學的人以及學別的科學的人。“因為我知道學文學的人讀莎士比亞,學音樂的人聽到音樂,他們所感受到的程度,他們心裏的感覺。這種感覺對我的工作也有很大的影響,它成為我做學問的一個標準。如果你有一個你所達不到的標準,你對你的工作就永遠不會滿意。”

視野的開闊,歲月的不斷積淀,使姚期智對人生有了更多的感悟,對社會有了更多的責任感。“我現在覺得可憂的是以前大家都看書,現在許多人都不看書了,而是看電視和玩遊戲。那種自然的、合作與交流的感覺在現代化的過程中喪失得太快。”

他認為,要對社會、對歷史有一定了解,那才不會隨波逐流。

溫總理的囑托

(圖)姚期智與溫總理(圖)姚期智與溫總理

2004年9月5日,溫家寶總理專程在教師節前來看望姚期智教授。在交談中,溫總理說,國家對人才的需求如飢似渴,高層次的人才是國家最稀缺、最寶貴的資源;我們在抓好基礎教育的同時,也要下大力氣抓好高等教育,為國家廣泛培養高層次優秀人才;在重點科研機構和重要科研領域,要實行傑出人才的全球招聘製度;要為傑出人才的脫穎而出和充分發揮作用創造良好的條件。

作為在國際一流大學長期任教的教授以及在電腦理論領域享有世界聲譽的學者,姚期智教授出任清華大學信息科學與技術國家實驗室(籌)學術委員會主任和首席科學家,立即承擔起建設世界一流的清華大學信息科學的重任,組織籌建國家實驗室。2004年10月22日,教育部部長周濟、副部長吳啓迪等領導來到清華大學考察信息科學與技術國家實驗室的籌建工作,專門與姚期智教授會面並聽取了他的匯報和建議。

我有嘉賓,鼓瑟吹笙

(圖)教學(圖)教學

姚先生回國定居後,主動和國內同行聯系,並親自走訪國內高校開展學術交流。同時,姚先生積極吸引世界最優秀的科學家來做訪問,他說,“讓年輕學者和學生接觸到這些專家,了解他們是怎麽做出一流水準的研究。”

2004年9月以來,姚先生定期聯系、邀請國內外知名大學教授來清華為學生做學術報告。不僅為學生提供了與國際一流學者交流的寶貴機會,還大大提升了學術講座的水準、豐富了學院的學術氣氛,至今已經組織過10場高水準的講座。開篇所說的兩位電腦科學領域的大師正是姚先生2005年邀請來華的。講座舉辦當天,許多慕名而來的學生把整個講堂擠得水泄不通,兩位大師深入淺出的精彩講演讓清華學子們真正領略到了名家風採。

為了使學生們能夠與這些世界級大師有更頻繁更深入的交流,姚先生計畫于下半年繼續邀請更多在電腦科學領域有突出貢獻的知名學者到清華訪問,並以“名家系列講座”的形式固定下來,作為講席教授組教學的一種重要輔助手段,長期地辦下去。

2005年3月16日,在北京市政府舉行的頒發儀式上,姚期智先生從北京市公安局局長馬振川手中接過了標志著北京永久居留權的“綠卡”。

個人榮譽

1987年 波裏亞獎(George Polya Prize)

1991 古根海姆基金會研究學者獎(Guggenheim Fellowship)

1995 美國電腦協會會士(Fellow, Association for Computing Machinery)

1996 高德納獎(Donald E. Knuth Prize)

1998 美國國家科學院院士(Member, US National Academy of Sciences)

姚期智姚期智

2000 美國人文科學院院士 (Fellow, American Academy of Arts and Sciences)

2000 圖靈獎(A.M. Turing Award)

2000 台灣中央研究院院士(Member, Academia Sinica)

2003 潘文淵研究考察獎 (Pan Wen-Yuan Research Award)

2003 香港城市大學理學榮譽博士(Doctor of Science, Honoris Causa, City University of Hong Kong)

2003 美國科學發展促進會會士(Fellow, American Association for the Advancement of Science)

2004 香港科技大學工學榮譽博士(Doctor of Engineering, Honoris Causa, Hong Kong University of Science and Technology)

2004 中國科學院外籍院士(Foreign Member, Chinese Academy of Sciences)

2004 伊利諾伊大學工程學院特殊貢獻校友獎(Alumni Award for Distinguished Service, College of Engineering, University of Illinois)

2006 香港中文大學理學榮譽博士(Doctor of Science, Honoris Causa, the Chinese University of Hong Kong)

2009 Doctor of Mathematics, Honoris Causa, University of Waterloo

2010 IACR Fellow

論文與著作

"Divergences of Massive Yang-Mills Theories: Higher Groups", (with S. L. Glashow and J. Illiopoulos), Physical Review, D4 (1971), 1918-1919.

2 "Standing Pion Waves in Superdense Matter", (with R. F. Sawyer), Physical Review, D7 (1973), 1579-1586.

3 "An O (|E| log log |V|) Algorithm for Finding Minimum Spanning Trees", Information Processing Letters, 4 (1975), 21-23.

4 "Analysis of the Subtractive Algorithms for Greatest Common Divisors", (with D. E. Knuth), Proceedings of the National Academy of Sciences USA, 72 (1975), 4720-4722.

姚期智姚期智

5 "On Computing the Minima of Quadratic Forms", Proceedings of Seventh ACM Symposium on Theory of Computing, Albuquerque, New Mexico, May 1975, 23-26.

6 "The Complexity of Non-uniform Random Number Generation" ,(with D. E. Knuth), in Algorithms and Complexity: New Directions and Recent Results, edited by J. F. Traub, Academic Press, 1976, pp.357-428.

7 "On the Evaluation of Powers", SIAM J. on Computing, 5 (1976), 100-103.

8 "Resource Constrained Scheduling as Generalized Bin Packing", (with M. R. Garey, R. L. Graham and D. S. Johnson), J. of Combinatorial Theory, A21 (1976), 257-298.

9 "Bounds on Merging Networks", (with F. F. Yao), Journal of ACM, 23 (1976), 566-571.

10 "Tiling with Incomparable Rectangles", (with E. M. Reingold and W. Sanders), Journal of Recreational Mathematics, 8 (1976), 112-119.

11 "A Combinatorial Optimization Problem Related to Data Set Allocation", (with C. K. Wong), Revue Francaise D'Automatique, Informatique, Recherche Operationnelle, Suppl. No. 5 (1976), 83-96.

12 "On a Problem of Katona on Minimal Separation Systems", Discrete Mathematics, 15 (1976), 193-199.

13 "An Almost Optimal Algorithm for Unbounded Searching", (with J. Bentley), Information Processing Letters, 5 (1976), 82-87.

14 "On the Average Behavior of Set Merging Algorithms", Proceedings of Eighth ACM Symposium on Theory of Computing, Hershey, Pennsylvania, May 1976, 192-195.

15 "The Complexity of Searching an Ordered Random Table", (with F. F. Yao), Proceedings of Seventeenth IEEE Symposium on Foundations of Computer Science, Houston, Texas, October 1976, 222-227.

16 "Probabilistic Computations: Toward a Unified Measure of Complexity", Proceedings of Eighteenth IEEE Symposium on Foundations of Computer Science, Providence, Rhode Island, October 1977, 222-227.

17 "On the Loop Switching Addressing Problem", SIAM J. on Computing, 7 (1978), 82-87.

18 "On Random 2-3 Trees", Acta Informatica, 9 (1978), 159-170.

姚期智姚期智

19 "K + 1 Heads are Better than K", (with R. L. Rivest), Journal of ACM, 25 (1978), 337-340.

20 "Addition Chains with Multiplicative Cost", (with R. L. Graham and F. F. Yao), Discrete Mathematics, 23 (1978), 115-119.

21 "The Complexity of Pattern Matching for a Random String", SIAM J. on Computing, 8 (1979), 368-387.

22 "A Note on a Conjecture of Kam and Ullman Concerning Statistical Databases ",Information Processing Letters, 9 (1979), 48-50.

23 "Storing a Sparse Table", (with R. E. Tarjan), Communications of ACM, 22 (1979), 606-611.

24 "On Some Complexity Questions in Distributive Computing", Proceedings of Eleventh ACM Symposium on Theory of Computing, Atlanta, Georgia, May 1979, 209-213.

25 "External Hashing Schemes for Collections of Data Structures", (with R. J. Lipton and A. L. Rosenberg), Journal of ACM, 27 (1980), 81-95.

26 "New Algorithms for Bin Packing", Journal of ACM, 27 (1980), 207-227.

27 "Information Bounds are Weak for the Shortest Distance Problem", (with R. L. Graham and F. F. Yao), Journal of ACM, 27, (1980), 428-444.

28 "A Stochastic Model of Bin Packing", (with E. G. Coffman, Jr., M. Hofri and K. So), Information and Control, 44 (1980), 105-115.

29 "An Analysis of Shellsort", Journal of Algorithms, 1 (1980), 14-50.

30 "On the Polyhedral Decision Problem", (with R. L. Rivest), SIAM J. on Computing, 9 (1980), 343-347.

31 "Bounds on Selection Networks", SIAM J. on Computing, 9 (1980), 566-582.

32 "Some Monotonicity Properties of Partial Orders", (with R. L. Graham and F. F. Yao), SIAM J. on Algebraic and Discrete Methods, 1 (1980), 251-258.

33 "A Note on the Analysis of Extendible Hashing", Information Processing Letters, 11 (1980), 84-86.

34 "Optimal Expected-Time Algorithm for Closest-point Problems", (with J. L. Bentley and B. W. Weide), ACM Trans. on Math. Software, 6 (1980), 561-580.

35 "Efficient Searching via Partial Ordering", (with A. Borodin, L. J. Guibas and N. A. Lynch), Information Processing Letters, 12 (1981), 71-75.

36 "An Analysis of a Memory Allocation Scheme for Implementing Stacks", SIAM J. on Computing, 10 (1981), 398-403.

37 "Should Tables be Sorted?", Journal of ACM, 28 (1981), 615-628.

38 "A Lower Bound for Finding Convex Hulls", Journal of ACM, 28 (1981), 780-787.

39 "The Entropic Limitations on VLSI Computations", Proceedings of Thirteenth ACM Symposium on Theory of Computing, Milwaukee, Wisconsin, May 1981, 308-311.

40 "Average-case Complexity of Selecting the k-th Best", (with F. F. Yao), SIAM J. on Computing, 11 (1982), 428-447.

41 "The Complexity of Finding Cycles in Periodic Functions", (with R. Sedgewick and T. G. Szymanski), SIAM J. on Computing, 11 (1982), 376-390.

姚期智姚期智

42 "On the Time-Space Tradeoff for Sorting with Linear Queries", Theoretical Computer Science, 19 (1982), 203-218.

43 "Lower Bounds to Algebraic Decision Trees", (with J. M. Steele, Jr.), Journal of Algorithms, 3 (1982),1-8.

44 "On Parallel Computation for the Knapsack Problem", Journal of ACM, 29 (1982), 898-903.

45 "On Constructing Minimum Spanning Trees in k-dimensional Spaces and Related Problems", SIAM J. on Computing, 11 (1982), 721-736.

46 "Equal Justice for Unequal Shares of the Cake", (with M. Klawe), Congressus Numerantium, 36 (1982), 247-260.

47 "Rearrangeable Networks with Limited Depth", (with N. Pippenger), SIAM J. on Algebraic and Discrete Methods, 3 (1982), 411-417.

48 "Space-Time Tradeoff for Answering Range Queries", Proceedings of Fourteenth ACM Symposium on Theory of Computing, San Francisco, California, May 1982, 128-136.

49 "Theory and Applications of Trapdoor Functions", Proceedings of Twenty-third IEEE Symposium on Foundations of Computer Science, Chicago, Illinois, November 1982, 80-91.

50 "Protocols for Secure Computations", Proceedings of Twenty-third IEEE Symposium on Foundations of Computer Science, Chicago, Illinois, November 1982, 160-164.

51 "On the Security of Public Key Protocols", (with D. Dolev), IEEE Trans. on Information Theory, 29 (1983), 198-208.

52 "Strong Signature Schemes", (with S. Goldwasser and S. Micali), Proceedings of Fifteenth ACM Symposium on Theory of Computing, Boston, Massachusetts, April 1983, 431-439

53 "Lower Bounds by Probabilistic Arguments", Proceedings of Twenty-fourth IEEE Symposium on Foundations of Computer Science, Tucson, Arizona, November 1983, 420-428.

54 "Context-free Grammars and Random Number Generation", Proceedings of NATO Workshop on Combinatorial Algorithms on Words, Maratea, Italy, July 1984, edited by A. Apostolico and Z. Galil, Academic Press, 357-361.

55 "Fault-tolerant Networks for Sorting", (with F. F. Yao), SIAM J. on Computing, 14 (1985), 120-128.

56 "On the Expected Performance of Path Compression", SIAM J. on Computing, 14 (1985), 129-133.

57 "On Optimal Arrangements of Keys with Double Hashing", Journal of Algorithms, 6 (1985), 253-264.

58 "Uniform Hashing is Optimal", Journal of the ACM, 32 (1985), 687-693.

59 "On the Complexity of Maintaining Partial Sums", SIAM J. on Computing, 14 (1985), 253-264.

60 "A General Approach to d-dimensional Geometric Queries", (with F. F. Yao), Proceedings of Seventeenth ACM Symposium on Theory of Computing, Providence, Rhode Island, May 1985, 163-168.

61 "Separating the Polynomial-time Hierarchy by Oracles", Proceedings of Twenty-sixth IEEE Symposium on Foundations of Computer Science, Eugene, Oregon, October 1985, 1-10.

62 "How to Generate and Exchange Secrets", Proceedings of Twenty-seventh IEEE Symposium on Foundations of Computer Science, Toronto, Canada, October 1986, 162-167.

姚期智姚期智

63 "Monotone Bipartite Graph Properties are Evasive", SIAM J. on Computing, 17 (1988), 517-520.

64 "Computational Information Theory", in Complexity in Information Theory, edited by Y. Abu-Mostafa, Springer-Verlag, 1988, 1-15.

65 "Selecting the k Largest with Median Tests", Algorithmica, 4 (1989), 293-300.

66 "On the Complexity of Partial Order Productions", SIAM J. on Computing, 18 (1989), 679-689.

67 "On the Improbability of Reaching Byzantine Agreement", (with R. L. Graham) Proceedings of Twenty-First ACM Symposium on Theory of Computing, Seattle, Washington, May 1989, 467-478.

68 "Circuits and Local Computations", Proceedings of Twenty First ACM Symposium on Theory of Computing, Seattle, Washington, May 1989, 186-196.

69 "Computing Boolean Functions with Unreliable Tests", (with C. Kenyon-Mathieu) International Journal of Foundations of Computer Science, 1 (1990), 1-10.

70 "Coherent Functions and Program Checkers", Proceedings of Twenty-second ACM Symposium on Theory of Computing, Baltimore, Maryland, May 1990, 84-94.

71 "On ACC and Threshold Circuits", Proceedings of Thirty-first IEEE Symposium on Foundations of Computer Science, October 1990, 619-627.

72 "Lower Bounds to Randomized Algorithms for Graph Properties", Journal of Computer and System Sciences, 42 (1991), 267-287.

73 "Lower Bounds for Algebraic Computation Trees with Integer Inputs", SIAM J. On Computing, 20 (1991), 655-668.

74 "Program Checkers for Probability Generation", (with S. Kannan) Proceedings of Eighteenth International Colloquium on Automata, Languages and Programming, Madrid, Spain, July 1991, 163-173.

75 "Linear Decision Trees: Volume Estimates and Topological Bounds", (with A. BjÖrner and L. Lovász) Proceedings of Twenty-fourth ACM Symposium on Theory of Computing, May 1992, 170-177.

76 "A Circuit-Based Proof of Toda's Theorem", (with R. Kannan, H. Venkateswaran and V. Vinay) Information and Computation, 104 (1993), 271-276.

77 "Towards Uncheatable Benchmarks", (with J. Cai, R. Lipton, and R. Sedgewick) Proceedings of Eighth IEEE Annual Structure in Complexity Conference, San Diego, California, May 1993, 2-11.

78 "Quantum Circuit Complexity", Proceedings of Thirty-fourth IEEE Symposium on Foundations of Computer Science, Palo Alto, California, November 1993, 352-361.

79 "A Randomized Algorithm for Maximum Finding with Parity Tests", (with H. F. Ting), Information Processing Letters, 49 (1994), 39-43.

80 "Near-Optimal Time-Space Tradeoff for Element Distinctness", SIAM J. On Computing, 23 (1994), 966-975.

81 "A Lower Bound for the Monotone Depth of Connectivity", Proceedings of Thirty-fifth IEEE Symposium on Foundations of Computer Science, Santa Fe, New Mexico, November 1994, 302-308.

82 "On Computing Algebraic Functions Using Logarithms and Exponentials", (with D. Grigoriev and M. Singer) SIAM J. on Computing, 24 (1995), 242-246.

83 "Algebraic Decision Trees and Euler Characteristics", Theoretical Computer Science, 141 (1995), 133-150.

84 "On the Shrinkage Exponent for Read-Once Formulae", (with J. Hastad and A. Razborov), Theoretical Computer Science, 141 (1995), 269-282.

85 "Minimean Optimal Key Arrangements in Hash Tables", Algorithmica, 14 (1995), 409-428.

86 "Security of Quantum Protocols Against Coherent Measurements", Proceedings of Twenty-seventh ACM Symposium on Theory of Computing, Las Vegas, Nevada, May 1995, 67-75.

87 "Decision Tree Complexity and Betti Numbers", Journal of Computer and Systems Sciences, 55 (1997), 36-43.

88 "Dictionary Look-Up with One Error", (with F. F. Yao), Journal of Algorithms, 25 (1997), 194-202.

89 "Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus", (with A. Razborov and A. Wigderson), Proceedings of Twenty-ninth ACM Symposium on Theory of Computing, May 1997, 739-784.

90 "RAPID: Randomized Pharmacophore Identification for Drug Design", (with L. Kavraki, J. Latombe, R. Motwani, C. Shelton, and S. Venkatasubramanian), Proceedings of 1997 ACM Symposium on Applied Computational Geometry, Nice, France, 1997, 324-333.

姚期智姚期智

91 "A Lower Bound on the Size of Algebraic Decision Trees for the MAX Problem", (with D. Grigoriev and M. Karpinski), Computational Complexity, 7 (1998), 193-203.

92 "Quantum Cryptography with Imperfect Apparatus", (with D. Mayers), Proceedings of Thirty-ninth IEEE Symposium on Foundations of Computer Science, October 1998, 503-509.

93 "NQP C = co - C = P", (with T. Yamakami), Information Processing Letters, 71 (1999), 63-69.

94 "Quantum Bit Escrow", (with A. Aharonov, A. Ta-Shma and U. Vazirani), Proceedings of Thirty-second ACM Symposium on Theory of Computing, May 2000, 715-724.

95 "Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity", (with A. Chakrabarti, Y. Shi and A. Wirth), Proceedings of Forty-second IEEE Symposium on Foundations of Computer Science, October 2001, 270-278.

96 "Classical Physics and the Church-Turing Thesis", Journal of ACM, 50 (2003), 100-105.

97 "On the Power of Quantum Fingerprinting", Proceedings of Thirty-fifth ACM Symposium on Theory of Computing, June 2003, 77-81.

98 "Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go?" (with X. Sun and S. Zhang), Proceedings of 19th IEEE Conference on Computational Complexity, Amherst, Massachusetts, June 2004, 286-293.

99 "Graph Entropy and Quantum Sorting Problems", Proceedings of Thirty-sixth ACM Symposium on Theory of Computing, June 2004, 112-117.

100 "Incentive Compatible Price Sequence in Dynamic Auctions", (with N. Chen, X. Deng and X. Sun), Proceedings of Thirty-first International Colloquium on Automata, Languages and Programming, Turku, Finland, July 2004 (Lecture Notes in Computer Science # 3142, Springer), 320-331.

101 "Fisher Equilibrium Price with a Class of Concave Utility Functions" (with N. Chen, X. Deng and X. Sun), Proceedings of Twelfth Annual European Symposium on Algorithms, Bergen, Norway, September 2004 (Lecture Notes in Computer Science # 3221, Springer), 169-179.

102 "Discrete and Continuous Min-energy Schedules for Variable Voltage Processors", (with M. Li and F. Yao), Proceedings of the National Academy of Sciences USA, 103 (2006), 3983-3987.

103 "On the Quantum Query Complexity of Local Search in Two and Three Dimensions", (With Xiaoming Sun), Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, October 2006, 429-438.

104 "A Note on Universal Composable Zero Knowledge in Common Reference String Model ", (With Frances F. Yao and Yunlei Zhao), The 4th Annual Conference on Theory and Applications of Models of Computation, Shanghai, China, May 2007

105 "A Note on the Feasibility of Generalized Universal Composability ", (With Frances F. Yao and Yunlei Zhao), The 4th Annual Conference on Theory and Applications of Models of Computation, Shanghai, China, May 2007

106 Graph Design for Secure Multiparty Computation over Non-Abelian Groups

姚期智姚期智

107 Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems

108 Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun, and Andrew Chi-Chih Yao Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems CCC 2008 2008

109 Xiaoming Sun, Andrew Chi-Chih Yao and Christophe Tartary Graph Design for Secure Multiparty Computation over Non-Abelian Groups Asiacrypt 2008

110 Xiaoming Sun, Andrew Chi-Chih Yao. On the Quantum Query Complexity of Local Search in Two and Three Dimensions in the following paginated issue of Algorithmica: Volume 55, Issue3 (2009), Page 576.

111 Andrew C.C. Yao, Frances F. Yao, Yunlei Zhao A Note on Universal Composable Zero Knowledge in Common Reference String Model Theoretical Computer Science 2009

112 Andrew C.C. Yao, Frances F. Yao, Yunlei Zhao A Note on the Feasibility of Generalized Universal Composability Mathematical Structure in Computer Science 2009

113 Andrew C. Yao, Moti Yung, and Yunlei Zhao, Concurrent Knowledge Extraction in the Public-Key Model, ICALP 2010

114 Andrew C. Yao and Yunlei Zhao. Deniable Internet Key Exchange, ACNS2010

相關詞條