China - 2000READ FULL CITATION AND ESSAY
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 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.
China - 1995
For significant research contributions in Computational Complexity, Analysis of Algorithms, Data Structures, Communication Complexity, and Cryptographic Protocols.