Andrew C. Yao
Born 24 December 1946, Shanghai, China
Turing Award 2000 “in recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudo random number generation, cryptography, and communication complexity”.
Andrew Yao was born in Shanghai. His family emigrated to Taiwan and he studied Physics at the National University of Taiwan (Bachelor of Science 1967). After his military service he continued his studies in Physics at Harvard (Master of Arts 1969, Ph.D. 1972). He added a second Ph.D. at the University of Illinois, this time in Computer Science (1975). He then worked as an assistant professor (1975-1976 MIT, 1976-1981 Stanford University), and subsequently as a professor in Computer Science (1981-1982 University of California, Berkeley, 1982-1986 Stanford University, 1986-2004 Princeton University). Since 2004, he has taught at Tsinghua University, Bejing, and has held a chair at the Chinese University of Hong Kong since 2005.
Aside from the ACM A.M. Turing Award, Yao has received many other prizes and awards, including the George Polya Prize (1987) and the Donald E. Knuth Prize (1996). He holds honorary degrees from the City University of Hong Kong, the Hong Kong University of Science and Technology, the Chinese University of Hong Kong, the Hong Kong Polytechnic University, the University of Macau, and the University of Waterloo.
Yao’s research in Computer Sciences is very broad, focusing on cryptography and the analysis of algorithms. He is particularly interested in the complexity of algorithms and of communication and associated questions: How long does it take a computer to solve a problem? How should that be measured, especially when the problem is solved using randomized methods? How can this be used to transfer data over secure channels? One of Yao’s most famous papers concerns the running time of randomized algorithms, that is, computer programs which play digital dice from time to time when solving a problem. If they are cleverly applied, these random decisions can accelerate an algorithm considerably; however, they can also make it slower. Using methods from mathematical game theory, Yao proposed a bridge between the worst running time of randomized algorithms and the mean running time of deterministic algorithms (algorithms that have no element of chance).
Computers have difficulties with random choice – they are built to do the same calculations exactly and always to give the same result. However, Yao developed a way to teach computers to generate numbers which look like random numbers by the means of ‘one-way functions’, and he showed how to test how far away these pseudo random numbers are from real random numbers. The idea of using one-way functions came from cryptography; random numbers often play a crucial role in allowing a provably secure data transfer. And random numbers play also a role in Yao’s famous solution of the millionaire’s problem, which can be formulated as a kind of game: Two millionaires want to compare their current account balance without telling the other how much money they have. The data transfer is supposed to be secure in this sense: the exact account balance has to be kept secret. Yao used mathematical tricks to show that this is in fact possible.