Andrew Chi-Chih Yao

Andrew Chi-Chih Yao is a computer scientist born in Shanghai, China^[1]. His work belongs to the theory of computation — the part of computer science that asks what can be computed, how efficiently, and with what guarantees. In 2000 he received the ACM A.M. Turing Award, whose citation named his fundamental contributions to that theory^[3]. Tsinghua University describes him as the first Chinese scientist to receive the Turing Award^[1][2].

Education

Yao earned an undergraduate degree in physics from Taiwan University^[1]. He continued in physics at Harvard University, receiving a PhD in 1972^[1]. Three years later he took a second doctorate, in computer science, from the University of Illinois in 1975^[1]. Training in physics and mathematics has been common among theoretical computer scientists, because the central questions of the field — how much time and memory a problem inherently requires — are mathematical in form and are answered by proof rather than by experiment.

The work behind the Turing Award

The 2000 ACM A.M. Turing Award was presented at the 2001 ACM Awards Banquet^[3]. The award was made "in recognition of his fundamental contributions to the theory of computation"^[3], and it singled out three connected areas: the complexity-based theory of pseudorandom number generation, cryptography, and communication complexity^[3].

Each of these concerns limits. A pseudorandom generator is a deterministic procedure that takes a short genuinely random seed and stretches it into a much longer string that no efficient procedure can distinguish from a truly random one. The complexity-based theory of such generators grounds their quality not in a claim that the output is unpredictable in principle, but in the assumed difficulty of a computational problem: if the problem is hard, distinguishing the output from random is hard too. Cryptography uses the same style of argument — an encryption scheme is secure if breaking it would require solving a problem believed to be intractable. Communication complexity asks a different kind of question: when the inputs to a function are split between two or more parties, how many bits must they exchange before they can all compute the answer? Proving that a problem needs a lot of communication rules out whole families of efficient protocols, and the same lower-bound techniques feed back into the study of pseudorandomness and secrecy. Bringing these questions into a single complexity-based framework is what the citation credits.

Teaching positions

Yao taught at MIT from 1975 to 1976, at Stanford University from 1976 to 1981 and again from 1982 to 1986, and at UC Berkeley from 1981 to 1982^[1]. In 1986 he joined Princeton University as the William and Edna Macaleer Professor of Engineering and Applied Science, and he remained there until he left for Tsinghua University in 2004^[1][2].

Return to China and institution building

Yao joined Tsinghua University in 2004^[2]. In 2005 he founded the Yao Class there, an undergraduate program for students aiming at research in computer science, and in 2011 he founded the Institute for Interdisciplinary Information Sciences (IIIS), of which he is dean^[2]. The two institutions are his attempt to build a base for theoretical computer science and for work that crosses computer science with other disciplines, inside a Chinese university.

Other honors

His other distinctions include the SIAM George Pólya Prize, the first ACM Donald E. Knuth Prize, membership of the US National Academy of Sciences, and foreign fellowship of the Chinese Academy of Sciences^[1]. Taken together, his career runs from the mathematical foundations of randomness and secrecy, through teaching at several of the leading American departments, to the building of research institutions in China.