Andrew C Yao

Digital Library

ACM A. M. Turing Award

China - 2000



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 gave the first convincing definition of a pseudorandom number generator; namely that its output sequences are not distinguishable from those of a truly random generator by any polynomial-time test. He proved that any generator satisfying the next bit test developed by Blum and Micali satisfied his definition, and showed that the discovery of any one-way function would lead to such a pseudorandom generator.

Dr. Yao introduced the important concept of communication complexity, which measures the minimum amount of interaction that two or more parties must have to jointly carry out some computation. He thus captured the essence of communication cost for distributed computation. His many contributions to complexity theory include proving the first exponential lower bound for the computation of an explicit function by a bounded-depth circuit. He has made seminal contributions to computational geometry, analysis of data structures, and quantum computing and communication.

ACM Fellows

China - 1995


For significant research contributions in Computational Complexity, Analysis of Algorithms, Data Structures, Communication Complexity, and Cryptographic Protocols.