姚期智

姚期智（Andrew Chi-Chih Yao）是出生于上海的中国计算机科学家^[1]。他的工作属于计算理论：这门学问追问的是什么能被计算、需要多少代价、能给出什么样的保证。2000年，他获得美国计算机学会（ACM）颁发的 A.M. 图灵奖（Turing Award），奖项给出的理由是「对计算理论的根本性贡献」^[3]。清华大学称他是第一位获得图灵奖的华人科学家^[1][2]。

教育背景

姚期智在台湾大学取得物理学本科学位^[1]。随后他到哈佛大学继续攻读物理，于1972年获得物理学博士学位^[1]。三年后，他又在伊利诺伊大学取得计算机科学博士学位^[1]。在理论计算机科学中，物理与数学出身的研究者并不少见：这个领域的核心问题是某个问题本质上需要多少时间和存储，而这类问题靠证明回答，不靠实验。

图灵奖背后的工作

2000年的 A.M. 图灵奖于2001年的 ACM 颁奖晚宴上颁发^[3]。授奖理由是「对计算理论的根本性贡献」^[3]，并特别提到三个相互关联的方向：基于复杂性的伪随机数生成理论、密码学，以及通信复杂性^[3]。

这三件事关心的都是「限度」。伪随机生成器是一个确定性程序：它取一小段真正随机的种子，把它拉长成一个长得多的串，而任何高效的程序都分辨不出这个串与真正的随机串有什么不同。基于复杂性的理论并不声称输出「本质上不可预测」，而是把它的质量建立在一个计算问题很难求解的假设上：只要那个问题足够难，把输出与随机区分开也同样难。密码学用的是同一种论证方式——如果一个加密方案被攻破就意味着解出了一个公认难解的问题，那么这个方案就是安全的。通信复杂性问的是另一类问题：当一个函数的输入被分给两方或多方时，他们要交换多少比特才能一起算出答案？证明某个问题需要大量通信，就一次性排除了整类高效协议；而这类下界技巧又反过来服务于伪随机性与保密性的研究。图灵奖所肯定的，正是把这些追问收进同一个基于复杂性的框架之中。

任教经历

姚期智于1975年至1976年在麻省理工学院任教，1976年至1981年、1982年至1986年两度在斯坦福大学任教，1981年至1982年在加州大学伯克利分校任教^[1]。1986年，他加入普林斯顿大学，出任 William and Edna Macaleer 工程与应用科学讲席教授，直到2004年离开、前往清华大学^[1][2]。

回到中国与建设机构

姚期智于2004年加入清华大学^[2]。2005年，他创办了以他名字命名的「姚班」，面向立志从事计算机科学研究的学生；2011年，他又创办了交叉信息研究院（Institute for Interdisciplinary Information Sciences，IIIS），并担任院长^[2]。这两个机构可以看作他的一项长期努力：在一所中国大学里，为理论计算机科学以及计算机科学与其他学科的交叉研究搭起一个基地。

其他荣誉

他的其他荣誉包括美国工业与应用数学学会（SIAM）的 George Pólya 奖、首个 ACM Donald E. Knuth 奖，以及美国国家科学院院士、中国科学院外籍院士^[1]。把这些串起来看，他的经历从随机性与保密性的数学基础出发，经过在美国几所顶尖院系的任教，最后落到在中国建设研究机构。