Andrew Chi-Chih Yao, the William and Edna Macaleer Professor of Engineering and Applied Science, has received the 2000 A.M. Turing Award from the Association for Computing Machinery.

This award, considered the Nobel Prize of Computing, was presented "in recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation, cryptography, and communication complexity."

Professor 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 two or more parties must have in order to jointly carry out some computation. Professor Yao thus captured the essence of communication cost for distributed computation.

Before Professor 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.

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.

Professor Yao, an alumnus of the National Taiwan University, earned a Ph.D. in physics from Harvard, and a Ph.D. in computer science from the University of Illinois. He is a fellow of the ACM and a member of the National Academy of Sciences, the American Academy of Arts and Sciences, and the Academia Sinica.

Professor Yao was recipient of the Guggenheim Fellowship, the SIAM George Polya Prize, and the ACM SIGACT-IEEE TCMFCS Donald E. Knuth Prize.