姚期智：开华裔获图灵奖的先河
世纪的第一个春天刚刚来临，从大洋彼岸就传来一个令人振奋的消息：
美国计算机学会(ACM)决定把2000年度的图灵奖授予华裔计算机科学家、
现普林斯顿大学教授姚期智。这是有“计算机世界的诺贝尔奖”之称的
图灵奖35年来首次授予一位华裔学者，是值得全世界华人为之骄傲的。
姚期智(Yao Chi-chih)的英文名字是安德鲁·姚(Andrew C.Yao)。
他祖藉湖北孝感，1946年12月24日出生于上海，幼年随父母去台湾省。1
967年在台湾大学毕业以后，去美国深造，原先所学专业是物理
。但20世纪60年代以来计算机技术的迅猛发展和计算机在各行各业的广
泛应用吸引了他的目光，他敏锐地意识到这是一个十分重要并具有巨大发
展空间的新兴学科，从而决心放弃原先专业而转到计算机科学上来。因此，
在1972年取得令人羡慕的哈佛大学物理学博士学位以后，他又来到伊利诺
大学研究生院继续学习。伊利诺大学在计算机科学技术方面处于美国领先地位。
姚期智于1975年在伊利诺大学取得他的第二个博士学位——计算机科学博士学位。
之后，他曾先后在麻省理工学院(1975～1976)、斯坦福大学(1976～1981，
1983～1986)、加州大学伯克利分校(1981～1983)等美国著名高等学府从事
教学与研究，1986年加盟普林斯顿大学至今。
姚期智对计算机科学技术所作出的贡献主要在计算理论方面。ACM在授奖
决定中指出，姚期智对计算理论的众多贡献是根本性的、意义重大的，
其中包括基于复杂性的伪随机数生成理论、密码学和通信复杂性。最近
1/4个世纪中姚期智发表的近百篇学术论文，几乎覆盖了计算复杂性的
所有方面。姚期智进入计算机科学领域最早的论文之一《寻找最小生成
树的O(|E|log log|V|)算法》一文就引起轰动，因为学术界原先认为，
寻找最小生成树算法的时间复杂度的下界是O(E log V)，而姚期智的论
文证明这个极限是可以打破的。在姚的这一开创性工作的基础上，经过近
20年的努力，人们终于设计出了寻找最小生成树的线性时间算法。
在数据组织方面，人们历来以为排序表(Sorted Table)是一种良好的结
构，在其中检索信息有最快的响应。姚期智经过深入研究，发现这只在少
数特定条件下才成立，而对于允许有任意信息编码的表而言，在排序表中
检索信息的效率远不是最佳的。他的研究结果在《表应该被排序吗?》一
文中发表以后，人们对信息应如何有效地存储在认识上发生了革命性的变
化。该文为后来出现最佳概率化哈希模式和字典实现方式奠定了基础。姚
在该文中所采用的证明方法则被称为“Cell Probe”模型而被广泛应用
，在数据结构和算法的分析与设计的研究中产生了深远的影响。
姚期智对伪随机数生成理论的诸多贡献集中反映在他1982年的论文《活板
门函数的理论和应用》中。在这篇有开创性意义的论文中，姚期智先证明
了著名的BlumMicali发生器所产生的随机数实际上是伪随机的，并由此
导出了在随机数生成技术中一个十分重要的概念，即“随机性和难度”的
折衷。论文还首次定义了“计算熵”(Computational Entropy)的概念，
对它进行了深入研究，引出了一系列有关定理和推论，推动了密码学的发
展。而姚期智自己则在1986年的论文《如何产生和交换秘密信息》中进一
步提出了一种称为“健忘的电路模拟”的密码技术，利用这种技术能秘密
而可靠地计算出任意函数。
随着Internet的普及和互联网的飞速发展，对通信复杂性的研究成为姚关
注的一个重点。他在这方面发表的论文如《电路和通信复杂性的近期进展》
被认为是经典之作，经常被其他论文引用。姚期智为通信建立了基本模型，
提出了分析方法，从而使通信复杂性发展成为一个重要的研究领域，并获
得了多方面的和意想不到的应用。
姚期智近期的研究集中于量子通信和计算。量子计算是以量子力学理论和
量子器件为基础、新近发展起来的一种新的计算技术，它不但能降低传统
计算技术的计算复杂性，还能解决一些传统计算机根本无法处理的问题。
姚期智在DARPA/ITO的资助下，已经在这方面的研究中取得若干成果，
发表了一些引人注目的论文，如《Quantum Bit Escrow》、
《Quantum Cryptography with Imperfect Apparatus》、
《Security of Quantum Protocol against Coherent Measurements》等。
在此次荣获图灵奖之前，姚期智在1996年获得以算法设计大师
克努特(Donald Ervin Knuth,1994年图灵奖获得者)命名的首
届克努特奖。去年4月，姚期智被选为美国艺术和科学院院士，
他也是我国《软件学报》(英文版)的副主编，曾到祖国内地参加学术活动。
姚期智的夫人弗朗西丝·姚(Frances F.Yao)也是来自中
国台湾省的华裔科学家，他们是志趣相投的一对伉俪，曾联名发表许多研究论文。
