博文
2000 A. M. TURING AWARD
||
中国骄傲真正的计算科学大师
信息来源：ACM
PRINCETON UNIVERSITY'S ANDREW CHI CHIH YAO WINS THE ASSOCIATION FOR COMPUTING MACHINERY'S 2000 A. M. TURING AWARD
New York, Feb. 1, 2001 -- The Association for Computing Machinery today announced the selection of Andrew Chi-Chih Yao as the winner of the 2000 A.M. Turing Award, considered the Nobel Prize of Computing.
Dr. Yao is receiving the award "in recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation, cryptography, and communication complexity."
Andrew Yao has helped shape the theory of computation. Yao established new paradigms and effective techniques in many areas including computational geometry, constant-depth Boolean circuit complexity, analysis of data structures, and quantum communication. He initiated the field of communication complexity, which measures the minimum amount of interaction that two or more parties must have in order to jointly carry out some computation. Yao thus captured the essence of communication cost for distributed computation.
Before Yao, the quality of a pseudorandom number generator was an empirical opinion. Yao gave the first convincing definition of a pseudorandom number generator, namely that its output sequences are not distinguishable from those of a truly random number generator by any polynomial-time test. He showed that any generator satisfying the specific "next-bit test" developed by Blum and Micali actually meets his general definition. He showed that the discovery of any one-way function would lead to such a pseudorandom number generator. This has great import for cryptography.
个人主页
从空白到知名：清华理论计算机专业的成长
https://blog.sciencenet.cn/blog-89075-43526.html
上一篇：计算科学哲学的先行者之一萨加德
下一篇：sedna
