Andrew C.-C. Yao

Andy's classic paper on Communication Complexity, perhaps the most quoted paper in Complexity Theory, introduced a fundamental model for communication and techniques for analyzing it. Communication Complexity has since developed into a major area, finding diverse and unexpected applications, with two books on the subject coming out soon.

In the paper "Should Tables Be Sorted," Andy revolutionized our view of efficient information storage, leading to the optimal probabilistic perfect hashing schemes and dictionary implementations. The same paper introduced the fundamental "Cell Probe" model for analyzing data structure algorithms, which is again a major object of study.

His paper on minimum spanning trees is a gem, showing the community via an O(E log log V)-time algorithm that the well-known O(E log V) time bound can be beaten. It took almost two decades to bring his O(E log log V) time result down to linear time.

The article "Theory and Applications of Trap-door Functions" contains an array of fundamental results. The most important is proving that the Blum-Micali generator is pseudo-random, leading to an important "hardness vs randomness" tradeoff: if one-way permutations exist, then BPP has subexponential deterministic simulations. It also defines and studies computational entropy, introduces the XOR lemma to amplify computational difficulty, and uses it to generate hard-core bits for every function.

In "How to Exchange Secrets" he introduces Oblivious Circuit Simulation, a fundamental cryptographic technique that enables private and secure computation of arbitrary functions. Previously such protocols were known for only a handful of examples.

Andy's sheer technical strength was always best revealed in Circuit Complexity. After the breakthrough superpolynomial lower bounds for constant depth circuits were proved, many subsequent attempts to construct exponential-depth lower bounds failed. Andy's tour-de-force "Separating the Polynomial-Time Hierarchy by Oracles" was a major accomplishment. For these as well as numerous other outstanding achievements, Andy Yao is awarded the first Knuth Prize.

Professor Yao received a Ph.D. from Harvard in 1972 in Physics and a second Ph.D. from the University of Illinois in Computer Science. Prior to joining the Princeton faculty, where he is a Full Professor in the Department of Computer Science, he held faculty positions at M.I.T., Berkeley, and Stanford. His award was presented at the 28th Annual ACM Symposium on Theory of Computing (STOC), held as part of the Federated Computing Research Conference in Philadelphia, PA, May 22-24, 1996.

The winner of the first Knuth Prize was chosen by an awards committee consisting of

- Ronald Graham, Chair (AT&T Research)
- Joe Halpern (IBM Almaden Research Center)
- Kurt Mehlhorn (Max-Planck-Institut für Informatik)
- Nicholas Pippenger (University of British Columbia)
- Eva Tardos (Cornell University)
- Avi Wigderson (Hebrew University)

Created by Ian Parberry, April 6, 1999.

Last updated Tue Apr 6 12:11:24 CDT 1999.