来客网

理论计算机科学近年的突破[中英文]

声明:本文转载自 「科技时空」, 或因排版与篇幅原因进行过编辑,内容未经本站独立核实,不代表本站立场、观点或建议。 如涉及版权问题,请联系我们,核实后立即删除。 [ 免责声明 ]

Yao: 姚期智(Andrew Chi-Chih Yao),计算机科学家,2000年图灵奖得主,是首位获得此奖项的华人。1986年至2004年任普林斯顿大学计算机科学系教授,从2004年9月至今任清华大学高等研究中心教授。姚期智是美国国家科学院院士、美国人文及科学院院士、中国科学院外籍院士及台湾中央研究院院士。

姚期智获得过美国工业与应用数学学会George Polya奖,美国计算机协会算法与计算理论分会(ACM SIGACT)Donald E.Knuth奖等荣誉。2000年,因为姚期智对计算理论,包括伪随机数生成,密码学与通信复杂度的诸多贡献,美国计算机协会(ACM)决定把该年度的图灵奖授予他。姚期智成为图灵奖创立以来首位获奖的华裔学者。

Teng: 滕尚华(Shang-Hua Teng)计算机科学家。目前是美国波士顿大学计算机系教授。与Spielman提出一种新的算法复杂度分析方法-----算法的平滑分析(smoothed analysis)。

Appendix A: Brief history of recent TCS breakthroughs

To illustrate our point about TCS making unexpected connections, we sketch the history of a few representative breakthroughs from the 1990s. Such connections are difficult to fund in the application-driven model.

* Boosting. Work in early 1980s (Yao’s work on hardness amplification for cryptography, Valiant’s PAC learning model) --> First “boosting” algorithm (Schapire, 1989) which was clearly impractical --> AdaBoost (Freund and Schapire, 1995); a practical algorithm that quickly became a pillar of AI, Data Mining, etc. (a recent textbook in the field calls it the ``best off-the-shelf classifier in the world''). It won the ACM Kanellakis 2004 award for theory & practice.

* Random graph models. Invented in 1959 (Erdos and Renyi) --> Studied in discrete mathematics and TCS for three decades which greatly refined our knowledge --> in late 1990s, became a popular and influential tool in reasoning about many large networks, including word nets, the internet, and the human brain, with connections to physics and biology (scale-free networks).

* Quantum computation. Suggested as a possibility by physicists (Feynman, Deutsch) in early 1980s --> early 1990s; STOC/FOCS papers (Bernstein-Vazirani, Yao, Simon) formalized quantum turing machines and quantum circuits, and suggested that they may be more powerful than classical computers because they can implement the Quantum Fourier Transform-->Shor’s factoring algorithm (1994) --> mid to late 1990s; TCS papers described how to introduce robustness in the quantum model and allow it to tolerate errors/decoherence --> today QC is a thriving sub area at the intersection of physics, chemistry, and CS.

* Hashing. Rudimentary forms discovered in 1950s -->First STOC/FOCS paper in 1979; universal hashing (Carter-Wegman)--> hashing theory developed over many years in TCS papers; few immediate applications --> Late 1990s, Akamai is formed thanks to the TCS idea of consistent hashing. Hashing-like ideas also heavily used by Google and other companies that work with large data-sets.

* Interactive and probabilistic proofs and an application to coding theory. Interactive proofs invented for cryptographic purposes (GMR, mid 1980s) --> in early 1990s, connection is made to probabilistically checkable proofs and leads to important extension of the classical theory of NP-completeness (namely, for many NP-hard problems, computing approximate solutions is NP-hard too) --> in late 1990s one of the offshoots is an algorithm for decoding error-correcting codes (Sudan, Guruswami-Sudan work on list-decoding) that is considered one of the major theoretical and practical advances in information and coding theory of the past decade (featured as a “discovery” on nsf.gov).

* PCPs and loss-resilient codes: PCP Theorem proved (1992, AS, ALMSS) -->1993 Sipser and Spielman rediscover expander codes in an effort to simplify proof of PCP Theorem--> late 1990s; new constructions of low density parity check codes (Luby, Mitzenmacher, Shokrollahi, and Spielman; cowinners of the 2002 IEEE Inf. Theory Society best paper award) --> 2000 and later; basis of major startup Digital Fountain, a new paradigm in coding theory, and basis of DVB-S2 standard for satellite transmission of television.

* Smoothed analysis: (Spielman and Teng, 2001) Combines worst-case analysis with average case analysis; a new paradigm for algorithm analysis that helps explain the everyday behaviour of some popular algorithms (such as the Simplex algorithm for linear programming).

评论 (0)