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
