Andrew Yao

Life and career

Andrew Chi-Chih Yao was born in Shanghai in 1946. His family left for Taiwan when he was a small child, and he grew up there, taking a bachelor's degree in physics at National Taiwan University. He came to the United States for graduate work and earned a PhD in physics from Harvard in 1972 — an unusual entry point for someone who would become one of the defining figures of theoretical computer science. Within a few years he had changed fields entirely, completing a second doctorate, this one in computer science, at the University of Illinois at Urbana-Champaign in 1975. The physics training is not incidental: Yao's characteristic style is to strip a computational situation down to its conserved quantities and then prove that a certain amount of something — bits, comparisons, rounds — simply cannot be avoided.

His American career took him through a series of the strongest departments in the country: MIT, Stanford, Berkeley, and then, from 1986, Princeton, where he held the William and Edna Macaleer Professorship of Engineering and Applied Science and spent two decades. During this period he produced the results that made his name — the communication complexity model, the minimax principle that bears his name, and the secure two-party computation protocol built on garbled circuits. In 2000 he received the ACM Turing Award, cited for fundamental contributions to the theory of computation, including complexity-based pseudorandom number generation, cryptography, and communication complexity. He was the first researcher of Chinese origin to win it.

In 2004 Yao did something few researchers at his career stage attempt: he left Princeton and moved to Tsinghua University in Beijing, giving up American academic life to build a research culture from scratch. He founded what became the Institute for Interdisciplinary Information Sciences and created an elite undergraduate track — universally known as the "Yao class" — designed to train Chinese students in theoretical computer science at a level competitive with the best in the world. By most accounts the program has succeeded dramatically; a substantial fraction of the strongest young Chinese theorists and AI researchers of the past two decades came through it, including several who have gone on to lead major research groups and companies. Yao renounced his U.S. citizenship and became a Chinese citizen, and was later elected an academician of the Chinese Academy of Sciences. His wife, Frances Yao, is also a distinguished theoretical computer scientist, known for work in computational geometry and algorithms.

The arc is worth noting for what it says about him. Yao's research contributions are about establishing what is unavoidable; his institutional work was about establishing what was, in his view, missing. Both are acts of construction from first principles.

Key contributions

**Communication complexity.** Yao's 1979 paper "Some Complexity Questions Related to Distributive Computing" introduced a model so clean that it now feels like it must always have existed. Two parties, conventionally Alice and Bob, each hold half of an input — Alice has $x$, Bob has $y$ — and they wish to compute $f(x,y)$. They have unlimited local computational power. The only resource being counted is *bits exchanged*. Stripping away computation and measuring communication alone turns out to expose structure invisible from other angles.

The canonical results are instructive. Deterministic equality testing on $n$-bit strings requires $\Theta(n)$ bits — you essentially have to send the whole input. But randomized equality testing needs only $O(\log n)$ bits, by hashing and comparing fingerprints. That gap is the entire theory of randomized algorithms in miniature. The lower-bound technique is combinatorial: the communication transcript partitions the input matrix into monochromatic rectangles, so a function whose matrix resists such partitioning is expensive to compute jointly. Fooling sets, rank bounds, and discrepancy arguments all fall out of that picture.

Communication complexity has become one of the most productive lower-bound frameworks in the field, precisely because so many other models reduce to it. Streaming algorithms, data-structure lower bounds, circuit depth, VLSI layout area, property testing, and distributed computing all inherit lower bounds from communication arguments. If you have ever seen a proof that a streaming algorithm must use $\Omega(n)$ memory, it almost certainly went through a reduction to set disjointness in the two-party model.

**Yao's minimax principle.** This is the technique that makes randomized lower bounds tractable. Proving that *every* randomized algorithm performs badly is awkward: the adversary must contend with the algorithm's coins. Yao's principle, an application of von Neumann's minimax theorem to the game between algorithm designer and input adversary, says that the expected cost of the best randomized algorithm on its worst-case input equals the cost of the best deterministic algorithm against the worst-case *input distribution*. So to prove a randomized lower bound, you exhibit a single hard distribution over inputs and show that no deterministic algorithm does well on average against it. That is a far easier object to reason about, and the principle is now standard equipment across algorithms, online computation, and complexity.

**Garbled circuits and secure two-party computation.** In the early 1980s Yao posed and solved what is now called the millionaires' problem: two people want to know who is richer without revealing their wealth. The general construction — Yao's garbled circuits — lets two parties jointly evaluate any Boolean circuit on their private inputs, learning the output and nothing else. One party encrypts the circuit gate by gate, replacing wire values with random labels and encrypting each gate's truth table under the appropriate label pairs; the other party obtains the labels for its own inputs via oblivious transfer and evaluates blindly. This is the founding construction of practical secure multiparty computation, and the modern MPC industry — private set intersection, privacy-preserving analytics, threshold cryptography deployments — descends directly from it.

**Pseudorandomness.** Yao also contributed a foundational result in the theory of pseudorandom generators, establishing the equivalence between *unpredictability* (no efficient algorithm can guess the next bit better than chance) and *indistinguishability* (no efficient algorithm can tell the output from truly random). The next-bit test is now the standard working definition of what a cryptographic generator must satisfy.

In battle

Yao's computed profile makes him one of the more well-rounded theorists on the roster. He carries 103 problems at a mean of 43.0 — noticeably higher than Cook's 37.8 or Blum's 35.9 — with 17 problems at 70 or above and only 21 at or below 20. His top categories are **high-dim** (71.5), **computability** (66.8 over sixteen problems), **games** (54.0 over thirteen), and **information** (52.0). That games number is distinctive: it reflects the minimax principle's roots in game theory, and it gives Yao a strong secondary front that most pure complexity theorists lack.

His ceiling problem is **P161, "How many bits must cross the wire"** (98) — literally the model he invented, down to the two-party framing and the equality-testing lower bound. **P287, "The router's memory is smaller than its traffic"** (95) is the streaming/sketching setting, where communication-complexity reductions are the standard source of space lower bounds; Yao is the reason those proofs exist. **P050, "Twenty questions with a liar"** (91) is a query-complexity and error-correction problem that sits squarely in his information-theoretic wheelhouse. **P170, "The message no eavesdropper can read"** (89) and **P164, "Trust without recomputing"** (85) reflect the cryptographic half of his career — garbled circuits, oblivious transfer, pseudorandomness. **P051, "The zero-sum room"** (86) is minimax itself, which he wields as a working tool rather than a historical curiosity. **P162, "More time, strictly more power"** (84) and **P031, "Is there a fast route through every city?"** (83) are standard complexity-theory ground.

The losses trace a clean boundary. Yao's floor problems are **P144, "The spam in the inbox"** (4) and **P136, "Counting accidents"** (4) — naive Bayes text classification and Poisson regression respectively. His `classification` average is 9.5 and his `perception` average is 9.0, the two lowest categories on his card, which is initially surprising for someone so strong on high-dimensional questions. The distinction is that Yao's high-dimensional strength is *combinatorial and information-theoretic* — how many bits, how many queries, what can a sketch preserve — not *statistical*. Ask him to bound what a sketch must lose and he is unbeatable; ask him to fit a classifier to labeled data and he has no method. **P069, "Edges before objects"** (10) and **P073, "Words from waveforms"** (8) are computer-vision and speech-recognition problems requiring signal-processing and pattern-recognition traditions he never worked in. **P107, "The thousand-year flood from thirty years"** (12) is extreme-value statistics; **P124, "Twenty thousand tests at once"** (10) is multiple-testing correction.

The practical guidance: Yao is the roster's best *lower-bound* fighter and one of its better all-around picks, with unusual breadth across theory, cryptography, and game theory. Field him when the question is "how much of this resource is unavoidable" — bits, rounds, memory, queries — or when it involves adversarial two-party settings or minimax reasoning. The stated battle identity is exact: he loses where constants and practice trump asymptotics, and he loses completely where the problem is one of estimating parameters from noisy real-world data rather than proving a bound on an abstraction.