姚期智(Andrew Chi-Chih Yao)，世界著名计算机学家，2000年图灵奖得主，美国科学院院士，美国科学与艺术学院院士，中国科学院外籍院士，清华大学高等研究中心教授。1967年获得台湾大学物理学士学位，1972年获得美国哈佛大学物理博士学位，1975年获得美国伊利诺依大学计算机科学博士学位。1975年至1986年曾先后在美国麻省理工学院数学系、斯坦福大学计算机系、加利福尼亚大学伯克利分校计算机系任助教授、教授。1986年至2004年在普林斯顿大学计算机科学系担任Wiliam and Edna Macaleer工程与应用科学教授。2004年起在清华大学任全职教授。

中文名：姚期智

外文名：Andrew Chi-Chih Yao

国籍：美国

出生地：上海

出生日期：1946年12月24日

职业：计算机学家

毕业院校：伊利诺依大学

主要成就：2000年图灵奖得主

职称：教授

工作单位：清华大学交叉信息研究院

姚期智简介(生平 成就)

中国情结

奋斗之路

成功理念

性格与成功

意外收获

温总理的嘱托

我有嘉宾鼓瑟吹笙

个人荣誉

论文与著作

从普林斯顿到水木清华

精耕细作的大师课堂

从根部解决问题

为中国作贡献刻不容缓

一次又一次零的突破

与中国学生天然的感情联系

姚期智简介

生平

（Prof. Yao Qizhi, Tsinghua University），祖籍湖北省孝感市孝昌县，1946年12月生于上海，著名物理学家，计算机学家。1967年获得台湾大学物理学士学位，1972年获得美国哈佛大学物理博士学位，1975年获得美国伊利诺依大学计算机科学博士学位；1975年至1986年先后在美国麻省理工学院数学系、斯坦福大学计算机系、加利福尼亚大学伯克利分校计算机系，普林斯顿大学等著名学府担任教授；1998年被选为美国科学院院士，2000年被选为美国科学与艺术学院院士。2004年当选为中国科学院外籍院士。

成就

多年来，姚期智先生以其敏锐的科学思维，不断向新的学术领域发起冲击，在数据组织、基于复杂性的伪随机数生成理论、密码学、通信复杂性乃至量子通信和计算等多个尖端科研领域，都做出了巨大而独到的贡献。他所发表的近百篇学术论文，几乎覆盖了计算复杂性的所有方面，并在获图灵奖之前，就已经在不同的科研领域屡获殊荣，曾获美国工业与应用数学学会乔治·波利亚奖和以算法设计大师克努特命名的首届克努特奖，是计算机理论方面国际上最拔尖的学者。

2007年3月29日，姚期智领导成立了清华大学理论计算机科学研究中心。

姚期智在理论计算机领域作研究至今，曾获美国工业与应用数学学会George Polya奖，美国计算机协会算法与计算理论分会(ACM SIGACT)Donald E.Knuth奖等荣誉。全球首要计算机协会(ACM)在2000年授予姚期智图灵奖。姚期智是图灵奖创立以来首位获奖的亚裔学者，也是迄今为止获此殊荣的唯一华裔计算机科学家。图灵奖是世界计算机科学领域的最高奖项，与物理、化学、医学、经济学领域的诺贝尔奖齐名。

2004年姚期智离开普林斯顿大学，到清华大学任全职教授。

姚期智之妻储枫（Frances Yao），自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

从普林斯顿到水木清华

3月29日,星期四。像往常一样,姚期智走进第六教学楼二层的一间教室。9点50分,软件科学实验班的课照常开始。

下午两点,姚期智把来自加州理工学院和奥克兰大学的两位学者请到信息科学技术大楼,给研究生开讨论课。

下午3点,姚期智向前来看望自己的教育部部长周济和科技部部长徐冠华汇报了两年多来在清华的工作进展,并与两位部长共同商讨世界一流学科的建设问题。

下午4点,会谈结束。姚期智开始科研、备课,直至深夜……

一个几乎没有间歇的忙碌的日子。对这位享誉世界的计算机“图灵奖”得主来说,是他在清华的平常一天。

精耕细作的大师课堂

全英文授课,全英文交流,讲台上经常出现来自世界各地的优秀学者。师生间没有拘束,学生们用流利的英语提问,问题尖锐而幽默,课堂上不时响起阵阵笑声。这就是软件科学实验班最普通的一堂课。

这样的课堂,让人很难想象,讲授的内容是艰深难懂的理论计算机科学。

软件科学实验班的每堂课都是精心设计的。每次上课,姚期智都会选择生动典型的实例,将学生引入到最根本的理论问题中。从清华到王府井怎么走路程最短?男女生如何选择约会对象成功率最高?教学楼里的自动售货机如何付款最划算?这些贴近学生生活的例子,大大激发了他们的兴趣和求知欲。

有一次,姚期智在课堂上“悬赏”出题,25分钟内解出者请吃“必胜客”。令他惊喜的是,90%的学生在规定时间内做出了正确的解答。姚期智信守承诺,按人数叫来近百份外卖,奖励了每位答对的学生。那天姚期智特别高兴,甚至半开玩笑地问学生:“你们以前有没有遇到过像我这么好的老师?”

在姚期智眼中,这是一群聪明可爱的学生。但姚期智并没有因为钟爱而放松对学生的要求,恰恰相反,他的课是出了名的容量大、习题多。所有作业必须以英文完成,而且要用专门的科学论文排版软件LaTeX来写。

对于姚期智的苦心,同学们大多能够理解。在清华2005—2006学年度春季学期对873门本科课程进行的学生问卷评估中,“理论计算机科学”课程居理论课前十位。

事实上,为了把握课程的难度,姚期智每周都会花很多时间和高研中心的孙晓明老师一起讨论;每次布置的作业题,姚期智也总会让孙晓明先做做看,感觉一下难度如何;为了防止学生“掉队”,姚期智请助教在每周的小班习题课上用中文讲解、答疑;第一年选课学生太多,姚期智还让5位助教分别“承包”一个小组,每周组织学生讨论课上遇到的问题。

从根部解决问题

除了带博士生做研究、指导本科生的毕业设计外,每周还要为本科生讲4小时的课,这是姚期智为自己定下的工作量。而他在普林斯顿任教时,只是每年按惯例为本科生和研究生各上一学期的课。

不辞辛劳,是因为他对清华的本科生寄予厚望。2006年春天着手创办软件科学实验班时,姚期智明确表示:“我们的目标并不是培养普通的计算机软件程序员,而是培养具有国际水平的一流计算机人才。”

回国之初,姚期智原本计划尽快构建一个培养博士生的良好机制,但随后在清华的亲身感受,让他逐渐萌生了人才培养从本科生开始的想法。姚期智在普林斯顿大学的“关门弟子”、目前在加州理工学院做博士后研究的张胜誉由衷钦佩老师的决心:“看到完善本科教育的重要性后,他不惜扎到最深处,从根部解决这个问题。他在本科生中开办软件科学实验班,自己一点点教起,这是很费气力的一件事。”

姚期智与微软亚洲研究院沈向洋院长一起探讨,为软件科学实验班制定培养方案,编写教学计划。按照这个计划,8门高水平核心课程分别由姚期智等知名教授和来自微软亚洲研究院的高级研究人员担纲,其中由姚期智亲自主讲的《理论计算机科学》是国内首次开设的计算机理论课程。

8门核心课程中,有4门课程由微软亚洲研究院的高层研究人员讲授,他们将最新的科研进展和课题引进教学。2006年秋,来自微软的教员竟然讲到了当时还未在中国上市的Vista操作系统——那时,很多讲授类似课程的教师都还无法获得任何有关Vista的具体资料。

培养方案将大四整整一年设置为实践教育和研究训练时间,地点在微软等国际知名的大IT公司,采用双导师制,以保证教学的规范性和工程实践的先进性。

“我们要多为学生提供增加基础理论知识的机会,同时也要不断丰富他们将理论用到实际方面的经验。唯有具备深厚的理论基础和主动学习的能力,他们才能适应未来的工作环境。”姚期智说。

为中国作贡献刻不容缓

2002年5月,在上海、南京和北京,姚期智第一次与国内计算机领域的学者进行了广泛接触和交流。那时,孙晓明和张胜誉都是清华计算机系的研究生。为了让学生一场不落地听完报告,姚期智在复旦演讲时,张胜誉的导师应明生教授将组里所有人都送到了上海。

所以接下来的“巧合”也许就有了某种必然性:张胜誉作为姚期智在普林斯顿的“关门弟子”赴美留学;孙晓明则成为姚期智在清华指导的第一位博士生。

正是在这次访问中,清华学生的聪敏好学给姚期智留下了深刻印象;次年,他欣然接受领衔组建计算机系讲席教授组的邀请;又过了一年,也就是2004年9月,姚期智辞去普林斯顿的终身教职,正式加盟清华高等研究中心,成为清华全职教授。他说:“对于建设世界一流大学,清华大学乃至中国政府都寄予了很大的期望。能在这份事业中贡献我的一份力量,可以算是一件大事。”

姚期智的夫人储枫教授非常支持他的这一决定。早在2003年,储枫从美国去香港城市大学担任计算机科学系系主任,也正是受到了先生的鼓励。储枫表示,姚期智是个很有决断力的人,不喜欢拖泥带水。他认为做这件事情能够为中国的高等教育、为中国的科学研究出力,所以很值得。最重要的是,清华有许多很好、很有潜力的学生,对他们的培养刻不容缓。

一次又一次零的突破

姚期智的全职回国,填补了国内计算机学科的空白:这不只是因为他无可争议的学术地位,更因为在他所从事的算法和复杂性领域,当时几乎还看不到中国国内学者的身影。而这一领域既是美国理论计算机科学的主流方向,又是计算机界最高奖项——“图灵奖”获奖人数最多的一个方向。

由此,清华的计算机学科第一次集齐了理论、应用、系统结构和软件四大领域的优秀学者,这在国际上也是不多见的。

姚期智带来了一个从6人增至10人的讲席教授组,他们都是国际上算法和复杂性领域最出色的华人学者。

随着姚期智的归来,清华计算机学科国际交流的频率和层次都达到了一个新的高度。以姚期智创建的理论计算机科学研究中心(ITCS)为例,2007年国外学者的访问日程已经安排到了12月31日。美国两院院士、1985年“图灵奖”得主RichardKarp,2002年“图灵奖”得主、著名密码学家AdiShamir……都曾出现在ITCS的访问学者名单上。

2006年,清华计算机系有3篇论文入选理论计算机科学领域与STOC并列的最顶级学术会议FOCS,不仅实现了国内学者在该会议上“零的突破”,而且入选篇数超过了美国计算机科学领域的“超一流”大学UCBerke-ley。更令人振奋的是,当年24岁的博士生陈汐与来自香港城市大学的讲席教授邓小铁合作,出色地解决了理论计算机科学的著名难题——二人博弈中纳什均衡点的复杂性问题,并因此获得2006年度FOCS最佳论文奖。

这一年,姚期智的团队还为国内计算机学者填补了在《美国科学院院刊》上发文的空白。

2007年4月16日—19日,理论计算机科学研究中心成功主办了第十届国际公钥密码学会议,来自世界15个国家的学者参会,姚期智担任大会主席。这是国际密码学研究领域和理论计算机研究方向的一次世界级盛会,首次在中国召开,又恰逢该会议的十周年庆典,可谓意义深远。

与中国学生天然的感情联系

对他的中国学生,姚期智给予了超乎寻常的爱心和耐心。他给学生买来舒适的座椅,为的是让他们喜欢来实验室,坐下来好好想问题;陈汐从美国波士顿大学交流回来后,姚期智专门和他探讨如何改进组里的工作,陈汐讲到的情况和建议,姚期智都认真记录下来;学生做例行报告时即使讲得不尽人意,姚期智也会耐心地听完,再指出不足之处。

姚期智喜欢给本科生上课。在他看来,给本科生上课与给研究生上课不同。怎样把一个理论解释给很聪明、但在这个领域还没有很多知识的本科生,往往需要想得更加深入。

谈到在普林斯顿与在清华教学的不同,姚期智说:“心理上的满足感会不一样。虽说‘科学无国界’,但是在为中国的年轻人讲解知识、看到他们真正吸收了的时候,心里会有特别的感觉,我想是有一种天然的感情联系吧。”

旗帜性人物归来的“放大效应”

2007年3月29日,教育部部长周济、科技部部长徐冠华共同到清华看望姚期智。周济强调,姚期智全职归来并带动一批人才回国发展,堪称一面“旗帜”。徐冠华也谈到,像姚期智这样的旗帜性人物回国,必然会产生“放大效应”。

姚期智回国两年半,不仅显著改变了国内理论计算机领域的研究面貌和学术水平,也在广大华人学者、学生中产生了潜移默化的影响。

讲席教授滕尚华注意到,现在有很多中国留学生回到北京,参加微软亚洲研究院理论组的招聘面试,这在10年前是不可想象的。至于他自己,以前回国往往只呆一周左右的时间,现在有了姚期智的理论计算机科学研究中心,他每次都会在北京呆大半个月甚至更久。他感觉到,在姚期智的影响下,北京正逐渐成为理论计算机科学的中心城市之一。

讲席教授组成员、香港城市大学邓小铁教授这样评价姚期智的归来:“清华请来姚先生,同时也带回了他在这个领域的影响力。从那以后,有很多知名科学家造访清华……一些顶尖的计算机科学家对我说,只要姚先生在这里工作,清华将会有越来越多有天分的学生进入理论计算机科学领域,并成为这一领域有影响力的人物。”

如何完善世界一流计算机学科建设的整体规划,如何吸引并留住一批顶尖人才、一个优秀团队,在中国共同建设一流的计算机学科,这是姚期智目前最关心的问题。他始终坚信,能够为中国的高等教育、为中国的科学发展出力,十分值得。