姚期智简介 计算机科学家姚期智生平简介
姚期智(英语: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月至今任北京清华大学高等研究中心教授。此外,姚期智还是美国国家科学院院士、美国人文及科学院院士、中国科学院外籍院士及台湾中央研究院院士。
姚期智获得过美国工业与应用数学学会波利亚奖(Pólya Prize),计算机协会算法与计算理论分会(ACM SIGACT)高德纳奖(Donald E.Knuth Prize)等荣誉。2000年,因为姚期智对计算理论,包括伪随机数生成,密码学与通信复杂性的诸多贡献,计算机协会(ACM)授予他该年度的图灵奖。
2007年3月29日,姚期智领导成立了中国清华大学理论计算机科学研究中心,并在2010年12月30日领导成立了中国清华大学交叉信息研究院。12月6日,姚期智在台湾国立清华大学应聘担任荣誉讲座。
姚期智之妻储枫(Frances Yao),2004年至2011年在香港城市大学计算机科学系担任系主任。
1967年,台湾大学,物理学学士学位
1972年,哈佛大学,物理学博士学位
1975年,伊利诺伊大学,计算机科学博士学位
回归清华
姚期智的全职回国，填补了国内计算机学科的空白：这不只是因为他无可争议的学术地位，更因为在他所从事的算法和复杂性领域，当时几乎还看不到中国国内学者的身影。而这一领域既是美国理论计算机科学的主流方向，又是计算机界最高奖项——“图灵奖”获奖人数最多的一个方向。
由此，清华的计算机学科第一次集齐了理论、应用、系统结构和软件四大领域的优秀学者，这在国际上也是不多见的。姚期智带来了一个从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个国家的学者参会，姚期智担任大会主席。这是国际密码学研究领域和理论计算机研究方向的一次世界级盛会，首次在中国召开，又恰逢该会议的十周年庆典，可谓意义深远。
家庭生活
姚期智的夫人储枫教授早在2003年从美国去香港城市大学担任计算机科学系系主任。
人物轶事
中国情结
姚期智人生头20年生活在中国，20岁以后生活在美国，57岁以后又将人生归宿在中国大陆的姚期智的人生轨迹宛如一个圆。
生在上海，长在台湾，却在美国接受了36年熏陶的姚期智自己也没有料到，在中国所接受的教育是如此根深蒂固，尤其是随着年龄的增长，也许是人生经验多了的缘故，姚期智对中国文化的感受更加深刻了。
姚期智是怀有中国情结的。姚期智说他在清华教育年轻一代，有一种满足感，是在美国教美国学生时所没有的。在这里，他教育的是中国年轻人！
姚期智表示“中国是我的祖国，我受中国传统文化的教育和影响是非常深厚的，我对整个中国的感情非常深厚。目前国内有一个很好的目标，要建设出几个世界一流的研究型大学来，我觉得我现在能在清华参与这件工作也算是一点小小的贡献。希望能尽点儿微薄之力。”
总理嘱托
2004年9月5日，温家宝总理专程在教师节前来看望姚期智教授。在交谈中，温总理说，国家对人才的需求如饥似渴，高层次的人才是国家最稀缺、最宝贵的资源；我们在抓好基础教育的同时，也要下大力气抓好高等教育，为国家广泛培养高层次优秀人才；在重点科研机构和重要科研领域，要实行杰出人才的全球招聘制度；要为杰出人才的脱颖而出和充分发挥作用创造良好的条件。
作为在国际一流大学长期任教的教授以及在计算机理论领域享有世界声誉的学者，姚期智教授出任清华大学信息科学与技术国家实验室（筹）学术委员会主任和首席科学家，立即承担起建设世界一流的清华大学信息科学的重任，组织筹建国家实验室。2004年10月22日，教育部部长周济、副部长吴启迪等领导来到清华大学考察信息科学与技术国家实验室的筹建工作，专门与姚期智教授会面并听取了他的汇报和建议。
人物著作
"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
