Andrew Yao

Andrew Chi-Chih Yao earned a PhD in physics at Harvard and then another in computer science before settling into complexity theory. In 1979 he founded communication complexity, and in 1982 he posed the millionaires' problem: two parties want to compute a function of their secret inputs without showing those inputs to each other. His answer, garbled circuits, encrypts an entire Boolean circuit gate by gate so it can be evaluated without exposing any intermediate value. That was the starting gun for secure multiparty computation, which Goldreich, Micali and Wigderson generalised in 1987.

The Turing Award came in 2000, in part for the complexity-based theory of pseudorandomness. In 2004 he left Princeton for Tsinghua in Beijing, where his elite programme, the Yao Class, has since produced a sizeable share of China's computer scientists. He also contributed to the circuit theory of quantum computing.