Andrew C Yao

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.