Award Has Been Called The "Nobel Prize Of Computing"

Award presented at 2001 ACM Awards Banquet in San Jose

The Association for Computing Machinery today presented Andrew Chi-Chih Yao with the 2000 A.M. Turing Award, at the Annual ACM Awards Banquet. The A.M. Turing award has been called the "Nobel Prize" of Computing. Each year, the banquet celebrates the achievements and contributions of computer science and information technology luminaries. Frederick P. Brooks, Jr. was the winner of the award in 1999, for landmark contributions to computer architecture, operating systems, and software engineering.

Dr. Yao received 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.

Dr. Yao has helped shape the theory of computation. He 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. Dr. Yao thus captured the essence of communication cost for distributed computation.

Before Dr. Yao, the quality of a pseudorandom number generator was an empirical opinion. He 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. Dr. Yao 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.

Biographical Background:

An alumnus of the National Taiwan University, he earned a Ph.D. in Physics at Harvard, and a Ph.D. in Computer Science from the University of Illinois.

Dr. Yao is a fellow of the ACM, a member of the National Academy of Sciences, American Academy of Arts and Sciences, and Academia Sinica. He was recipient of the Guggenheim Fellowship, the SIAM George Polya Prize, and the ACM SIGACT-IEEE TCMFCS Donald E. Knuth Prize.

Prior to his current position at Princeton as William and Edna Macaleer Professor of Engineering and Applied Science, Dr. Yao taught at MIT, Stanford University, and the University of California, Berkeley. He was also a consultant at IBM, DEC Systems Research Center, and Xerox Palo Alto Research Center.

Dr. Yao has been Managing Editor of the SIAM Journal on Computing, and Advisory Editor for the Journal of Combinatorial Optimization. He has served on the editorial boards of Algorithmica, Information and Control, the Journal of the ACM, the Journal of Algorithms, Random Structures & Algorithms, and the Journal of Cryptology.

His professional activities include the American Association for the Advancement of Science, the American Mathematical Society, the ACM, the IEEE, and the Society for Industrial and Applied Mathematics. He was co-organizer of the 1990-1991 NSF Discrete Mathematics and Theoretical Computer Science (DIMACS) Special Year in Complexity Theory, and Co-Director of DIMACS from 1994 to 1996.

The A.M. Turing Award

A prize of $25,000 accompanies ACM's most prestigious technical award. It is given to an individual selected for contributions of a technical nature made to the computing community.

The contributions should be of lasting technical importance to the computer field.

2000 ACM Award Winners:

A.M. Turing Award: Andrew Chi-Chih Yao Princeton University