|
|
CONTACT: Anne P. Wilson
IMMEDIATE
New York, Feb. 1, 2001 -- The Association for Computing Machinery today announced the selection of Andrew Chi-Chih Yao as the winner of the 2000 A.M. Turing Award, considered the Nobel Prize of Computing. Dr. Yao is receiving the award "in recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation, cryptography, and communication complexity." Andrew Yao has helped shape the theory of computation. Yao established new paradigms and effective techniques in many areas including computational geometry, constant-depth Boolean circuit complexity, analysis of data structures, and quantum communication. He initiated the field of communication complexity, which measures the minimum amount of interaction that two or more parties must have in order to jointly carry out some computation. Yao thus captured the essence of communication cost for distributed computation. Before Yao, the quality of a pseudorandom number generator was an empirical opinion. Yao gave the first convincing definition of a pseudorandom number generator, namely that its output sequences are not distinguishable from those of a truly random number generator by any polynomial-time test. He showed that any generator satisfying the specific "next-bit test" developed by Blum and Micali actually meets his general definition. He showed that the discovery of any one-way function would lead to such a pseudorandom number generator. This has great import for cryptography. Background An alumnus of the National Taiwan University, he earned a Ph.D. in Physics at Harvard, and a Ph.D. in Computer Science from the University of Illinois. Dr. Yao is a fellow of the ACM, a member of the National Academy of Sciences, American Academy of Arts and Sciences, and Academia Sinica. He was recipient of the Guggenheim Fellowship, the SIAM George Polya Prize, and the ACM SIGACT-IEEE TCMFCS Donald E. Knuth Prize. Prior to his current position at Princeton as William and Edna Macaleer Professor of Engineering and Applied Science, Dr. Yao taught at MIT, Stanford University, and the University of California, Berkeley. He was also a consultant at IBM, DEC Systems Research Center, and Xerox Palo Alto Research Center. Editorial Boards Dr. Yao has been Managing Editor of the SIAM Journal on Computing, and Advisory Editor for the Journal of Combinatorial Optimization. He has served on the editorial boards of Algorithmica, Information and Control, the Journal of the ACM, the Journal of Algorithms, Random Structures & Algorithms, and the Journal of Cryptology. His professional activities include the American Association for the Advancement of Science, the American Mathematical Society, the ACM, the IEEE, and the Society for Industrial and Applied Mathematics. He was co-organizer of the 1990-1991 NSF Discrete Mathematics and Theoretical Computer Science (DIMACS) Special Year in Complexity Theory, and Co-Director of DIMACS from 1994 to 1996. The A.M. Turing Award A prize of $25,000 accompanies ACM's most prestigious technical award. It is given to an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting technical importance to the computer field. ACM will present the Turing Award to Dr. Yao at the annual ACM Awards Banquet, on March 11, 2001 at the Fairmont Hotel, San Jose. ACM Founded in 1947, ACM (www.acm.org) is the world's first educational and scientific computing society. With more than 80,000 members worldwide, a dynamic series of authoritative publications, the ACM Digital Library, with one of the most respected online collections of computer science information, a wide range of special interest groups (SIGs), and an outstanding array of conferences, workshops and forums, ACM is a world-class resource for the entire technology field. |
