Andrew Yao

Andrew Chi-Chih Yao is a Chinese-American computer scientist whose work shaped computational complexity, cryptography, and quantum computing. He received the 2000 Turing Award for foundational contributions to these fields.

Yao's minimax principle: A theorem equating randomized decision-tree complexity with a maximum distributional complexity over input distributions. It turns lower bounds for randomized algorithms into distributional lower-bound proofs.
Yao's XOR lemma: A theorem showing that solving the XOR of many independent instances requires strong performance on the underlying problem. It amplifies hardness, connecting Yao’s complexity work to cryptographic security.
Tsinghua University: A major research university in Beijing, founded in 1911. Yao studied physics there before moving to the United States for graduate study.
Miklos Santha: A theoretical computer scientist known for work on randomized and quantum computation. Santha and Yao collaborated on quantum walk algorithms and query complexity.
Secure multiparty computation: Cryptographic protocols that let multiple parties compute jointly while protecting their private inputs. Yao’s garbled circuits provide a classic way to realize two-party secure computation.
Communication complexity: The study of how much information parties must exchange to compute a function of jointly held inputs. Yao introduced communication complexity as a framework for proving computational lower bounds.
Yao's garbled circuits: A cryptographic technique that lets one party evaluate a function while concealing its inputs and intermediate computation. Yao introduced the method as a foundation for secure two-party computation.
Harvard University: A private research university in Cambridge, Massachusetts, founded in 1636. Yao earned a doctorate in physics at Harvard in 1969.
David Zuckerman: A computer scientist whose research includes pseudorandomness, derandomization, and complexity theory. Yao’s minimax framework is closely connected to Zuckerman’s work on randomness and lower bounds.
Oblivious transfer: A cryptographic protocol in which a sender transfers selected information without learning the recipient’s choice. Yao used oblivious transfer in foundational work on secure two-party computation.

Linked from 1 page

Adi ShamirRelated: Yao's work on secure computation belongs to the same theoretical cryptography tradition Shamir helped develop.