Princeton University (2000)
Citation
"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.

He received the Turing Award, the most prestigious award in computer science, in 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".

Yao was born in Shanghai, China. He completed his undergraduate education in physics at the National Taiwan University, before completing a PhD in physics at Harvard University in 1972, and then a second PhD in computer science from the University of Illinois.

He had been a Professor of Computer Science at Princeton University, where he continues to work on algorithms and complexity. In 2004, he became a Professor of Computer Science at Tsinghua University, Beijing, China.