5月28日，美国计算机协会（ACM：the Association for Computing Machinery）的算法和
计算机理论专业组（SIGACT：Special Interest Group on Algorithms and Computing
Theory）宣布，滕尚华教授及其合作者荣获2008年哥德尔（Godel）奖。
滕尚华是美国波士顿大学计算机系教授，卡耐基梅隆大学博士。主要研究方向为计算几何、
最优化、互联网算法等。他们此次的获奖工作是Smoothed Analysis of Algorithms: Why
the Simplex Algorithm Usually Takes Polynomial Time。
哥德尔奖是理论计算机科学领域的最高奖项之一，由EATCS和ACM SIGACT共同评选
(http://sigact.acm.org/prizes/godel/, for outstanding papers)，与美国工业与应用
数学学会（SIAM)乔治·波利亚奖(George Polya Prize,
http://www.siam.org/prizes/sponsored/polya.php, to recognize specific recent
work)和ACM SIGACT以算法设计大师克努特命名的克努特奖(Knuth Prize,
http://sigact.acm.org/prizes/knuth/, for major research accomplishments and
contributions over an extended period of time)齐名。
滕尚华1985年获得上海交通大学计算机、电子双学位。他也是Akamai科技公司的高级研究人
员，清华大学姚期智讲席教授组成员。他曾在麻省理工学院的数学系、明尼苏达大学和伊利
诺大学香槟分校的计算机科学系任教。他和MIT的Dan Spielman一起，发展了以建模和分析
实际算法为目标的平滑分析理论，并且示范了线性规划的单纯形算法具有多项式平滑复杂
性。这项工作被国家科学基金会（FY’03）所支持。他的研究关注于高效算法设计和实现。
他的研究兴趣还包括光谱技术优化和信息处理、并行科学计算、计算几何、超大规模集成电
路和线路模拟、组合优化和可能性分析、分布式计算和密码学。在编译器优化和因特网技术
方面，他获得过7项美国专利。
算法的复杂度分析是软件系统设计与分析中的一个重要环节.为了分析算法的复杂度,我们
常常对算法进行最坏情况复杂度分析.长期以来,人们一直为这样的现象所困惑,有很多算
法按通常的(最坏情况)分析具有很坏的复杂度(通常是指数级的),但在实际应用中却很有
效.这类算法的一个典型代表就是优化问题的单纯形算法.20世纪80年代初,人们用随机方
法分析了单纯形算法,并证明了对输入参数的一系列分布,单纯形算法的期望执行时间收敛
于多项式复杂度.但是,在随后20年里,很多人的研究指出,这种统计平均的多项式复杂度并
不能很好地解释单纯形算法的实际有效性,因为它的输入参数的统计分布具有很特殊的性
质,在实际应用中很罕见.另外,算法的平均复杂度与输入实例空间上的概率分布有关,不同
的分布其相应的平均复杂度未必相同,而且输入实例空间上的概率分布一般不容易得知.
为了更合理地解释这样的现象,美国麻省理工学院的Daniel A.Spielman与波士顿大学的
滕尚华提出了计算机算法的平滑复杂度(smoothed complexity)概念.Spielman和Teng
在STOC 2001的论文[1]中提出了一种新的算法复杂度分析方法,即算法的平滑复杂度分析.
他们的思路是这样的,在分析一个算法时,对输入实例加上合理的微小幅度的随机"扰动",
然后分析执行时间与输入规模及扰动的关系,由此得出的时间复杂度称为该算法的时间平
滑复杂度.分析算法的平滑复杂度,其目的在于探测输入实例空间中是否含有最坏输入实例
的稠密区域.Spielman和Teng在文献[1]中分析了"两阶段投影-顶点"单纯形算法的平滑复
杂度,证明了"两阶段投影-顶点"单纯形算法在具有给定规模的所有可能的输入实例的局部
随机邻域上,其最高平均时间复杂度是多项式的,更合理地解释了单纯形算法虽然具有很坏
的最坏情况复杂度(时间复杂度为指数级),但在实际应用中却很有效之间的矛盾.自文献
[1]发表以来,这一领域的研究在理论计算机界引起了极大的关注并取得了一系列的成果[2].
[1] Spielman DA, Teng SH. Smoothed analysis of algorithms: Why the simplex
algorithm usually takes polynomial time. In: SIGACT,ed. Proc. of the 33rd
Annual ACM Symp. on Theory of Computing. ACM Press, 2001. 296~305.
http://www-math.mit.edu/~spielman/SmoothedAnalysis/papers.html
[2] Spielman DA, Teng SH. Smoothed analysis of algorithms. In: LI T, ed. Proc.
of the 2002 Int'l Congress of Mathematicians,Abstracts of Plenary and Invited
Lectures. Beijing: Higher Education Press, 2002. 144~145.
http://www-math.mit.edu/~spielman/SmoothedAnalysis/papers.html
