# Andrew Yao

> Source: https://aiwiki.ai/wiki/andrew_yao
> Updated: 2026-07-24
> Fact-checked: 2026-07-24
> Categories: AI Safety, Chinese AI, Computer Science, People
> License: CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) - attribute to "AI Wiki (aiwiki.ai)"
> Cite as: AI Wiki. "Andrew Yao." aiwiki.ai, 24 Jul 2026. https://aiwiki.ai/wiki/andrew_yao
> From AI Wiki (https://aiwiki.ai), the free encyclopedia of artificial intelligence. Reuse freely with attribution.

Andrew Chi-Chih Yao (Chinese: 姚期智, Yao Qizhi; born December 24, 1946) is a computer scientist who received the 2000 ACM A.M. Turing Award and who has spent the past two decades building computer science and artificial intelligence programs in China. His theoretical work in the late 1970s and 1980s produced several of the tools that modern complexity theory and cryptography still run on: the minimax argument now called Yao's principle, the field of communication complexity, the complexity-based treatment of pseudorandomness, and the two constructions that started secure multiparty computation, the millionaires' problem and garbled circuits [1][2].

Yao spent nearly thirty years on the faculties of MIT, Stanford, the University of California, Berkeley, and Princeton before moving to [Tsinghua University](https://aiwiki.ai/wiki/tsinghua_university) in 2004 [2]. There he founded an undergraduate program known as the Yao Class in 2005, the Institute for Interdisciplinary Information Sciences (IIIS) at the end of 2010, the Shanghai Qi Zhi Institute in 2020, and Tsinghua's College of AI in April 2024 [3][4][5][6]. He renounced his United States citizenship in 2015 and was converted from foreign member to full academician of the [Chinese Academy of Sciences](https://aiwiki.ai/wiki/chinese_academy_of_sciences) on February 21, 2017 [7].

Since roughly 2023 Yao has also become one of the most visible Chinese voices on frontier [AI safety](https://aiwiki.ai/wiki/ai_safety), serving as a convener of the International Dialogues on AI Safety and co-authoring the 2024 Science paper "Managing extreme AI risks amid rapid progress" alongside [Yoshua Bengio](https://aiwiki.ai/wiki/yoshua_bengio) and [Geoffrey Hinton](https://aiwiki.ai/wiki/geoffrey_hinton) [8][9].

## Early life and education

Yao was born in Shanghai on December 24, 1946. His family moved briefly to Hong Kong and then to Taiwan, where he took a B.S. in physics from National Taiwan University in 1967 [2]. He went to [Harvard University](https://aiwiki.ai/wiki/harvard_university) for graduate work in physics, earning an A.M. in 1969 and a Ph.D. in 1972 under Sheldon Glashow, who won the Nobel Prize in Physics in 1979 [2].

Yao then switched fields. He entered the computer science doctoral program at the University of Illinois Urbana-Champaign and finished in 1975 with a dissertation titled "A Study of Concrete Computational Complexity," supervised by Chung Laung Liu [2]. Two doctorates within three years of each other left him with an unusual profile for a theorist: a physicist's training applied to questions about algorithms and information.

## Academic career in the United States

Yao's first appointment was in the mathematics department at [MIT](https://aiwiki.ai/wiki/mit) for the 1975-1976 academic year. He joined [Stanford University](https://aiwiki.ai/wiki/stanford_university) as an assistant professor of computer science in 1976, moved to [UC Berkeley](https://aiwiki.ai/wiki/uc_berkeley) as a professor in 1981, returned to Stanford as a full professor in 1982, and in 1986 became the William and Edna Macaleer Professor of Engineering and Applied Science at Princeton, where he stayed until 2004 [1][2][7]. He has been a Distinguished Professor-at-Large at the Chinese University of Hong Kong since 2005 and has supervised more than twenty doctoral students [2].

## Theoretical contributions

### Yao's principle

Yao's 1977 paper "Probabilistic Computations: Toward a Unified Measure of Complexity," presented at the 18th IEEE Symposium on Foundations of Computer Science, introduced what is now called Yao's principle or Yao's minimax principle [2][10]. It states that the best achievable expected cost of a randomized algorithm on its worst-case input equals the best achievable expected cost of a deterministic algorithm on the hardest input distribution [10].

The result follows from von Neumann's minimax theorem applied to a zero-sum game in which one player picks an algorithm and the other picks an input, and the optimal strategies on each side can be computed as dual [linear programs](https://aiwiki.ai/wiki/linear_programming) [10]. The practical payoff is a proof technique: to show that no randomized algorithm can beat a given bound, it suffices to exhibit one input distribution on which every deterministic algorithm is slow. That weaker inequality form is what most lower-bound proofs actually use, and it applies to comparison-based sorting and selection, graph property testing, black-box optimization, communication protocols, and the competitive analysis of online and caching algorithms [10].

### Communication complexity

In "Some Complexity Questions Related to Distributive Computing," presented at STOC 1979, Yao defined the two-party communication model that carries the field's name [11]. Alice holds an input x, Bob holds an input y, and the two must jointly compute f(x, y) while exchanging as few bits as possible; the deterministic communication complexity D(f) is the worst-case bit count of the best protocol [11].

The model turned out to be a general-purpose lower-bound engine. Bounds proved in it transfer to decision tree complexity, VLSI circuit area, data structures, and streaming algorithms, because each of those settings can be made to simulate a communication protocol [11]. Yao's paper also introduced randomized communication complexity and the gap it opens: equality testing needs n bits deterministically but only O(log n) bits with shared randomness [11]. His 1993 FOCS paper "Quantum Circuit Complexity" extended the framework to [quantum computing](https://aiwiki.ai/wiki/quantum_computing) [4].

### Pseudorandomness and the next-bit test

Yao's FOCS 1982 paper "Theory and Applications of Trapdoor Functions" is the source of the complexity-based theory of pseudorandom generation named in his Turing Award citation [1][4]. The paper formalizes one-way functions as easy to compute and hard to invert on a large fraction of inputs, and proposes what Yao called a computational information theory that refines Shannon's, including notions of computational entropy that later became central to leakage-resilient cryptography [2].

The same paper introduced the next-bit test: a bit sequence passes if no efficient adversary that has seen the first i bits can predict bit i+1 with probability meaningfully better than one half [12]. Yao proved that passing the next-bit test is not merely necessary but sufficient for passing every polynomial-time statistical test, which reduced the question "is this generator pseudorandom" to a single, checkable condition [12].

### Secure computation, the millionaires' problem, and garbled circuits

Also in 1982, in "Protocols for Secure Computations" at FOCS, Yao posed the millionaires' problem: two people want to learn which of them is richer without either revealing how much money they have [13]. Stated formally, given private numbers a and b, the parties must jointly decide whether a is at least b and learn nothing else [13]. The question opened the study of secure multiparty computation, where mutually distrustful parties evaluate a joint function over private inputs with no trusted third party [14].

Yao's answer arrived in a technique now called the garbled circuit. One party, the garbler, converts a Boolean circuit into an encrypted form by assigning two random labels to each wire, one representing 0 and one representing 1, then encrypts each row of every gate's truth table under the corresponding input labels and randomly permutes the rows so the row order leaks nothing [14]. The evaluator obtains labels for its own inputs through oblivious transfer, which reveals neither the evaluator's choice to the garbler nor the unselected label to the evaluator, and then decrypts its way through the circuit to the output [14]. The construction is secure against semi-honest adversaries, meaning parties that follow the protocol but try to learn what they can from the transcript [14].

The publication history is unusual. The technique appeared implicitly in the 1982 paper and was presented orally at FOCS 1986 alongside "How to Generate and Exchange Secrets"; the first written description was by Goldreich, Micali, and Wigderson at STOC 1987, and the name "garbled circuit" was coined by Beaver, Micali, and Rogaway at STOC 1990 [2][14]. Garbled circuits are now practical at scale, including for privacy-preserving matching against DNA databases [2], and they sit alongside [homomorphic encryption](https://aiwiki.ai/wiki/homomorphic_encryption_ml), [differential privacy](https://aiwiki.ai/wiki/differential_privacy), and [federated learning](https://aiwiki.ai/wiki/federated_learning) in the modern privacy-preserving machine learning toolkit.

### The Dolev-Yao model

With Danny Dolev, Yao published "On the Security of Public Key Protocols" at FOCS 1981, later expanded in IEEE Transactions on Information Theory in 1983 [4][15]. The paper defines the adversary model still used as the default in symbolic protocol analysis: the attacker controls the entire network and can overhear, intercept, replay, and synthesize messages, but cryptography is treated as perfect, so the attacker cannot decrypt without the key or guess keys [15]. Separating network control from cryptographic strength made automated protocol verification tractable [15].

### Selected papers

| Year | Paper | Venue | What it introduced |
| --- | --- | --- | --- |
| 1977 | Probabilistic Computations: Toward a Unified Measure of Complexity | FOCS | Yao's principle (minimax principle) |
| 1978 | Should Tables Be Sorted? | FOCS | Cell-probe model of data structures |
| 1979 | Some Complexity Questions Related to Distributive Computing | STOC | Communication complexity |
| 1981 | On the Security of Public Key Protocols (with D. Dolev) | FOCS | Dolev-Yao adversary model |
| 1982 | Theory and Applications of Trapdoor Functions | FOCS | Next-bit test, computational entropy |
| 1982 | Protocols for Secure Computations | FOCS | Millionaires' problem, secure computation |
| 1985 | Separating the Polynomial-Time Hierarchy by Oracles | FOCS | Oracle separation of PH |
| 1986 | How to Generate and Exchange Secrets | FOCS | Garbled circuits |
| 1993 | Quantum Circuit Complexity | FOCS | Quantum circuit complexity |

Paper titles and venues are as listed in Yao's DBLP bibliography [4].

## Awards

Yao received the [Turing Award](https://aiwiki.ai/wiki/turing_award) in 2000 with the 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" [1]. He had been named an ACM Fellow in 1995 for research contributions in computational complexity, analysis of algorithms, data structures, communication complexity, and cryptographic protocols [1], and in 1996 he became the first recipient of the Knuth Prize [16].

| Year | Honor | Awarding body |
| --- | --- | --- |
| 1987 | Pólya Prize | SIAM |
| 1995 | ACM Fellow | ACM |
| 1996 | Knuth Prize (inaugural) | ACM SIGACT |
| 1998 | Member, National Academy of Sciences | NAS |
| 2000 | A.M. Turing Award | ACM |
| 2000 | Academician | Academia Sinica |
| 2021 | Kyoto Prize, Advanced Technology | Inamori Foundation |
| 2024 | Basic Science Lifetime Award | International Congress of Basic Science |

The 2021 Kyoto Prize in Advanced Technology, in the information science field, was given for "Pioneering Contributions to a New Theory of Computation and Communication and a Fundamental Theory for Its Security" [3]. The 2024 Basic Science Lifetime Award, presented in the Theoretical Computer and Information Sciences category at the International Congress of Basic Science in Beijing, cited "groundbreaking work that has deeply influenced theoretical computer science" [17].

## Tsinghua, the Yao Class, and IIIS

Yao left Princeton for Tsinghua University in 2004, joining its Center for Advanced Study and becoming director of the university's Institute for Theoretical Computer Science [2]. In 2005 he founded the Computer Science Experimental Class within Tsinghua's Xuetang honors program, universally known as the Yao Class [5]. The program was designed to give Chinese undergraduates a computer science education comparable to what MIT and Stanford offer, and Yao oversees its curriculum and teaches in it himself [5][18].

The Institute for Interdisciplinary Information Sciences was established on December 30, 2010, absorbing the earlier theoretical computer science institute, and Yao became its dean in January 2011 [7][18]. IIIS added a Center for Quantum Information on January 6, 2011 [5]. Yao Class undergraduates now choose among three tracks: computer science, artificial intelligence, and quantum information [5].

In 2020 Yao founded the Shanghai Qi Zhi Institute, a research institution in Shanghai that works on foundational AI alongside cryptography, quantum computing, [embodied AI](https://aiwiki.ai/wiki/embodied_ai), and biological intelligence [6]. On April 27, 2024, Tsinghua established a College of AI with Yao as its founding dean; the college's stated aim is breakthroughs in "the core foundations, underlying architecture and future computing models of AI," organized around research lines that include novel theory and efficient algorithms, embodied intelligence and multimodal perception, AI security governance, and future computing substrates such as optoelectronic and quantum hardware [19]. TIME reported in September 2024 that Yao had established four AI institutes across China since 2018 [20].

## Influence on the Chinese AI industry

The Yao Class is the clearest channel through which Yao has shaped [China's AI sector](https://aiwiki.ai/wiki/china_ai). TIME's 2024 profile of Yao credited his students with founding multibillion-dollar companies and named [Megvii](https://aiwiki.ai/wiki/megvii) and [Pony.ai](https://aiwiki.ai/wiki/pony_ai) specifically, with others taking faculty positions at Stanford and Princeton [20]. The Wire China reported in July 2026 that Yao Class alumni founded both companies and that graduates of the program work at Meta and Google [21].

Two documented cases give the pattern concrete form. Yin Qi entered the Yao Class in 2006, graduated in 2010, worked on [facial recognition](https://aiwiki.ai/wiki/facial_recognition) at Microsoft Research Asia, and co-founded Megvii in October 2011 with Tang Wenbin and Yang Mu; Megvii went on to build the Face++ platform and the MegEngine deep learning framework [22]. Danqi Chen graduated from the Yao Class in 2012, completed a Stanford Ph.D. under Christopher Manning in 2018, and has been on the faculty of Princeton since 2019, where she works on natural language processing and open-domain question answering [23][24]. Pony.ai, the [autonomous driving](https://aiwiki.ai/wiki/autonomous_driving) company co-founded in December 2016 by James Peng and Tiancheng Lou, listed on Nasdaq in November 2024 and added a Hong Kong listing in November 2025; Lou had begun doctoral study at Yao's IIIS in 2008 [25][31].

Tsinghua's broader AI ecosystem extends past the Yao Class. The Wire China notes that [Zhipu AI](https://aiwiki.ai/wiki/zhipu_ai), the developer of the GLM open models, and DeepLang AI were both incubated at Tsinghua by alumni or faculty of its AI institutes, and that Tsinghua alumni had founded 18 embodied AI companies by 2025 [21]. Yao's own institutes are one strand in that ecosystem rather than the whole of it.

## AI safety and governance

Yao is the third listed author, after Bengio and Hinton, on "Managing extreme AI risks amid rapid progress," published in Science in 2024 and posted to arXiv in an initial version in October 2023 [9]. The paper argues that governance and technical safety work are lagging capability growth and that autonomous AI systems could produce large-scale social harms, malicious use, and irreversible loss of human control [9].

He is one of the main conveners of the International Dialogues on AI Safety, a series of closed meetings between Chinese and Western researchers [8]. He signed the consensus statements from IDAIS-Beijing in March 2024, IDAIS-Venice in September 2024, IDAIS-Shanghai in July 2025, and IDAIS-London in April 2026, where the group called on states to treat proliferation of AI-enabled cyberattack and biological misuse capability as a common threat [26][27]. On those statements Yao is listed as dean of the Shanghai Qi Zhi Institute and dean of both IIIS and the College of AI at Tsinghua [27]. He also holds a leadership role in the China AI Safety and Development Association, the Chinese network that presented at the Paris AI Action Summit in February 2025, though outside analysts describe that body as an international engagement platform rather than a domestic regulator with staff and budget [8][28].

Speaking at the [World Artificial Intelligence Conference](https://aiwiki.ai/wiki/world_artificial_intelligence_conference) in 2024, Yao framed the risk in unusually blunt terms, saying that humanity has "suddenly found a way to create a new species that is many, many times more powerful than we are" and that "if we don't do anything, we are going to be eliminated" [8]. In 2026 he chaired WAICA, a new academic conference launched alongside the World Artificial Intelligence Conference in Shanghai and co-chaired by Richard Sutton; its submission process accepts multimedia artifacts and combines AI-assisted checks, public real-name review, and expert evaluation, with a verification platform intended to make submitted research runnable and reproducible [29].

## Recent research

Yao continues to publish. He is a co-author of "Tensor Product Attention Is All You Need," posted to arXiv on January 11, 2025, which introduces tensor product attention (TPA) and the T6 architecture built on it [30]. TPA factorizes queries, keys, and values into low-rank tensor components so that the [KV cache](https://aiwiki.ai/wiki/kv_cache) shrinks at inference time, which allows [longer contexts](https://aiwiki.ai/wiki/long_context) under a fixed memory budget while matching or beating standard [attention](https://aiwiki.ai/wiki/attention) baselines [30]. His group also published on [automated theorem proving](https://aiwiki.ai/wiki/automated_theorem_proving) in 2025, including ProofAug at [ICML](https://aiwiki.ai/wiki/icml) and "Hierarchical Attention Generates Better Proofs" at ACL, and earlier co-authored the Conflux blockchain paper "A Decentralized Blockchain with High Throughput and Fast Confirmation" at USENIX ATC 2020 [4].

Yao is married to Frances Yao (储枫), a computer scientist who works on computational geometry, algorithms, and cryptography and who chaired the computer science department at City University of Hong Kong from 2004 to 2011 [2][7].

## See also

- [Turing Award](https://aiwiki.ai/wiki/turing_award)
- [Tsinghua University](https://aiwiki.ai/wiki/tsinghua_university)
- [China AI](https://aiwiki.ai/wiki/china_ai)
- [Megvii](https://aiwiki.ai/wiki/megvii)
- [Pony.ai](https://aiwiki.ai/wiki/pony_ai)
- [AI safety](https://aiwiki.ai/wiki/ai_safety)

## References

1. ACM Awards, "Andrew C Yao: A.M. Turing Award (2000) and ACM Fellows (1995) citations." https://awards.acm.org/award_winners/yao_1611524
2. ACM A.M. Turing Award, "Andrew Chi-Chih Yao" laureate biography. https://amturing.acm.org/award_winners/yao_1611524.cfm
3. Inamori Foundation, Kyoto Prize laureate profile: Andrew Chi-Chih Yao, 2021 Advanced Technology (Information Science). https://www.kyotoprize.org/en/laureates/andrew_chi-chih_yao/
4. DBLP computer science bibliography, "Andrew Chi-Chih Yao." https://dblp.org/pid/y/AndrewChiChihYao.html
5. Institute for Interdisciplinary Information Sciences, Tsinghua University (English site). https://iiis.tsinghua.edu.cn/en/
6. Shanghai Qi Zhi Institute, "Embodied AGI theme forum at WAIC," July 7, 2023 (states the institute was founded in 2020 by Yao Qizhi). https://sqz.ac.cn/en/comprehensive-news-37
7. Chinese Wikipedia, "姚期智" (Yao Qizhi). https://zh.wikipedia.org/wiki/%E5%A7%9A%E6%9C%9F%E6%99%BA
8. Scott Singer, Karson Elmgren, and Oliver Guest, "How Some of China's Top AI Thinkers Built Their Own AI Safety Institute," Carnegie Endowment for International Peace, June 16, 2025. https://carnegieendowment.org/research/2025/06/how-some-of-chinas-top-ai-thinkers-built-their-own-ai-safety-institute
9. Yoshua Bengio, Geoffrey Hinton, Andrew Yao, et al., "Managing extreme AI risks amid rapid progress," arXiv:2310.17688 (published in Science, doi:10.1126/science.adn0117). https://arxiv.org/abs/2310.17688
10. Wikipedia, "Yao's principle." https://en.wikipedia.org/wiki/Yao%27s_principle
11. Wikipedia, "Communication complexity." https://en.wikipedia.org/wiki/Communication_complexity
12. Wikipedia, "Next-bit test." https://en.wikipedia.org/wiki/Next-bit_test
13. Wikipedia, "Yao's Millionaires' problem." https://en.wikipedia.org/wiki/Yao%27s_Millionaires%27_problem
14. Wikipedia, "Garbled circuit." https://en.wikipedia.org/wiki/Garbled_circuit
15. Wikipedia, "Dolev-Yao model." https://en.wikipedia.org/wiki/Dolev%E2%80%93Yao_model
16. ACM SIGACT, "Knuth Prize" recipient list. https://www.sigact.org/prizes/knuth.html
17. Wikipedia, "Basic Science Lifetime Award." https://en.wikipedia.org/wiki/Basic_Science_Lifetime_Award
18. Wikipedia, "Institute for Interdisciplinary Information Sciences." https://en.wikipedia.org/wiki/Institute_for_Interdisciplinary_Information_Sciences
19. College of AI, Tsinghua University (English site). https://collegeai.tsinghua.edu.cn/en/
20. TIME, "Andrew Yao," TIME100 AI 2024, September 5, 2024. https://time.com/7012855/andrew-yao/
21. The Wire China, "Tsinghua's Central Role in China's AI Revolution," July 19, 2026. https://www.thewirechina.com/2026/07/19/tsinghuas-central-role-in-chinas-ai-revolution/
22. Chinese Wikipedia, "印奇" (Yin Qi). https://zh.wikipedia.org/wiki/%E5%8D%B0%E5%A5%87
23. Chinese Wikipedia, "陈丹琦" (Danqi Chen). https://zh.wikipedia.org/wiki/%E9%99%88%E4%B8%B9%E7%90%A6
24. Wikipedia, "Danqi Chen." https://en.wikipedia.org/wiki/Danqi_Chen
25. Wikipedia, "Pony.ai." https://en.wikipedia.org/wiki/Pony.ai
26. International Dialogues on AI Safety, dialogue index. https://idais.ai/dialogues/
27. International Dialogues on AI Safety, "IDAIS-London," April 17-19, 2026. https://idais.ai/dialogue/idais-london/
28. Karson Elmgren, Scott Singer, and Oliver Guest, "Is China Serious About AI Safety?" AI Frontiers, October 14, 2025. https://ai-frontiers.org/articles/is-china-serious-about-ai-safety
29. 36Kr, "China's AI Establishes World-Class Academic Event WAICA," February 25, 2026. https://eu.36kr.com/en/p/3698417555976071
30. Yifan Zhang, Yifeng Liu, Huizhuo Yuan, Zhen Qin, Yang Yuan, Quanquan Gu, and Andrew Chi-Chih Yao, "Tensor Product Attention Is All You Need," arXiv:2501.06425, January 11, 2025. https://arxiv.org/abs/2501.06425
31. Chinese Wikipedia, "楼天城" (Lou Tiancheng). https://zh.wikipedia.org/wiki/%E6%A5%BC%E5%A4%A9%E5%9F%8E