Andrew Yao

Tsinghua University

Andrew Chi-Chih Yao is a Chinese-American computer scientist and professor at Tsinghua University who received the 2000 ACM Turing Award for his fundamental contributions to the theory of computation. Yao is best known for Yao's minimax theorem — a fundamental result in game theory and randomized algorithms showing that the optimal expected cost of any randomized algorithm equals the optimal expected cost against an adversarial input distribution — and for Yao's principle, which provides a powerful lower bound technique for randomized algorithms. He also developed communication complexity theory — the study of the amount of information that must be exchanged between players to compute a function — which has become one of the most influential areas in theoretical computer science with applications to circuit complexity, data streaming, and quantum computing. Yao contributed to circuit complexity, quantum information theory (Yao's garbled circuits), and the theory of pseudorandom generators. He played a major role in developing China's theoretical computer science community at Tsinghua.