1996 Knuth Prize

1996 Knuth Prize
Andrew C.-C. Yao

The recipient of the first Knuth Prize is Prof. Andrew C.-C. Yao of Princeton University, who is being honored for his fundamental research in computational complexity. For 25 years Andy Yao has been producing research papers in almost every aspect of computational complexity and many aspects of algorithmic design. These results and proof methods have typically caused a leap in the community's understanding of some central issue, enabling rejuvenated research by others. We list several examples as illustrations.

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


Created by Ian Parberry, April 6, 1999.
Last updated Tue Apr 6 12:11:24 CDT 1999.