Education:Yao, Andrew Chi-Chih.«Ŕ´Á´Ľ
Chi: hsin-chi (week); Chih: chih-huei (wisdom)William and Edna Macalcer Professor of Engineering and Applied Science (since 1986)
Dept. of Computer Science, Princeton University
B.S., National Taiwan University
PhD (physics), Harvard University, 1972
PhD (computer science), University of Illinois, 1975Honors:
Member, National Academy of Sciences (elected 1998)
see announcement from SIAM
Member, American Academy of Arts and Sciences
Member, Academia Sinica (Taiwan) elected 2000
ACM's A.M. Turing Award (2000), considered a Nobel in computing
(see also below)
SIAM's George Pólya Prize, 1987
the Donald E. Knuth Prize
Fellow, Association of Computing Machinery
Fellow, John Simon Guggenheim Memorial Foundation, 1991
Professional Experiences:
He has taught at MIT, Stanford, Berkeley, before coming to Princeton University in 1986.
Professor Yao's research interest is in computational complexity and analysis of algorithms. His activities are in the design of efficient computer algorithms, and complexity theories in emerging new areas of theoretical computer science, such as quantum communication and computing. He is investigating new paradigms for designing fast quantum algorithms, and mathematical tools for the security analysis of quantum cryptographic protocols. Professor Yao is also interested in exploring how far existing algorithms are from the best possible, in terms of the amount of computing resources (such as running time) required. He is studying this problem within the framework of the Boolean Circuit Model, in which computations are performed by networks composed of elementary logic gates. A concrete goal is to show that certain natural problems, such as the ``Traveling Salesman's Problem,'' cannot be computed by Boolean circuits of depth logarithmic in its input lengths. Such results would have much implications in computing theory far beyond the circuit model under which the results are derived.
Publications:
from SIAMAndrew Chi-Chih Yao. On the evaluation of powers. SIAM Journal on Computing, 5(1):100-103, March 1976. Citations.
Andrew Chi-Chih Yao. On the loop switching addressing problem. SIAM Journal on Computing, 7(4):515-523, November 1978.
Andrew Chi-Chih Yao. The complexity of pattern matching for a random string. SIAM Journal on Computing, 8(3):368-387, August 1979.
Andrew C. Yao and Ronald L. Rivest. On the polyhedral decision problem. SIAM Journal on Computing, 9(2):343-347, May 1980. Citations.
Andrew Chi-Chih Yao. Bounds on selection networks. SIAM Journal on Computing, 9(3):566-582, August 1980. Citations.
Andrew C. Yao. An analysis of a memory allocation scheme for implementing stacks. SIAM Journal on Computing, 10(2):398-403, May 1981.
Robert Sedgewick, Thomas G. Szymanski, and Andrew C. Yao. The complexity of finding cycles in periodic functions. SIAM Journal on Computing, 11(2):376-390, May 1982. Citations.
Andrew C. Yao and F. Frances Yao. On the average-case complexity of selecting the kth best. SIAM Journal on Computing, 11(3):428-447, August 1982.
Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721-736, November 1982. Citations.
Andrew C. Yao and F. Frances Yao. On fault-tolerant networks for sorting. SIAM Journal on Computing, 14(1):120-128, February 1985. Citations.
Andrew C. Yao. On the expected performance of path compression algorithms. SIAM Journal on Computing, 14(1):129-133, February 1985.
Andrew C. Yao. On the complexity of maintaining partial sums. SIAM Journal on Computing, 14(2):277-288, May 1985. Citations.
Andrew Chi-Chih Yao. Monotone bipartite graph properties are evasive. SIAM Journal on Computing, 17(3):517-520, June 1988.
Andrew Chi-Chih Yao. On the complexity of partial order productions. SIAM Journal on Computing, 18(4):679-689, August 1989.
Andrew Chi-Chih Yao. Lower bounds for algebraic computation trees with integer inputs. SIAM Journal on Computing, 20(4):655-668, August 1991. Citations.
Andrew Chi-Chih Yao. Near-optimal time-space tradeoff for element distinctness. SIAM Journal on Computing, 23(5):966-975, October 1994. References.
Dima Grigoriev, Michael Singer, and Andrew Yao. On computing algebraic functions using logarithms and exponentials. SIAM Journal on Computing, 24(2):242-246, April 1995. References and Citations.
from DBLP Bibliography
Andrew Chi-Chih Yao
List of publications from the DBLP Bibliography Server - FAQ
--------------------------------------------------------------------------------
2001
97 EE Andrew Chi-Chih Yao: Some perspective on computational complexity (abstract). STOC 2001: 6002000
96 EE Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao: Quantum bit escrow. STOC 2000: 705-7141999
95 Tomoyuki Yamakami, Andrew Chi-Chih Yao: NQPC = co-C=P. Information Processing Letters 71(2): 63-69 (1999)1998
94 EE Dominic Mayers, Andrew Chi-Chih Yao: Quantum Cryptography with Imperfect Apparatus. FOCS 1998: 503-509
93 EE Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao: An exponential lower bound on the size of algebraic decision trees for Max. Computational Complexity 7(3): 193-203 (1998)
92 EE Tomoyuki Yamakami, Andrew Chi-Chih Yao: NQP = co-C=P. Electronic Colloquium on Computational Complexity (ECCC) 5(73): (1998)1997
91 EE Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao: Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. STOC 1997: 739-748
90 Andrew Chi-Chih Yao, Frances F. Yao: Dictionary Look-Up with One Error. J. Algorithms 25(1): 194-202 (1997)
89 Andrew Chi-Chih Yao: Decision Tree Complexity and Betti Numbers. JCSS 55(1): 36-43 (1997)1996
88 Andrew Chi-Chih Yao: Hypergraphs and Decision Trees (Abstract). WG 1996: 11995
87 Andrew Chi-Chih Yao, F. Frances Yao: Dictionary Loop-Up with Small Errors. CPM 1995: 387-394
86 EE Andrew Chi-Chih Yao: Security of quantum protocols against coherent measurements. STOC 1995: 67-75
85 Andrew Chi-Chih Yao: Minimean Optimal Key Arrangements in Hash Tables. Algorithmica 14(5): 409-428 (1995)
84 EE Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao: An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX. Electronic Colloquium on Computational Complexity (ECCC) 2(57): (1995)
83 Dima Grigoriev, Michael F. Singer, Andrew Chi-Chih Yao: On Computing Algebraic Functions Using Logarithms and Exponentials. SIAM J. Comput. 24(2): 242-246 (1995)
82 Andrew Chi-Chih Yao: Algebraic Decision Trees and Euler Characteristics. TCS 141(1&2): 133-150 (1995)
81 Johan Hĺstad, Alexander A. Razborov, Andrew Chi-Chih Yao: On the Shrinkage Exponent for Read-Once Formulae. TCS 141(1&2): 269-282 (1995)1994
80 Andrew Chi-Chih Yao: A Lower Bound for the Monotone Depth of Connectivity. FOCS 1994: 302-308
79 Andrew Chi-Chih Yao: Decision Tree Complexity and Betti Numbers. STOC 1994: 615-624
78 Hing-Fung Ting, Andrew Chi-Chih Yao: A Randomized Algorithm for Finding Maximum with O((log n)˛) Polynomial Tests. Information Processing Letters 49(1): 39-43 (1994)
77 Andrew Chi-Chih Yao: Near-Optimal Time-Space Tradeoff for Element Distinctness. SIAM J. Comput. 23(5): 966-975 (1994)1993
76 Andrew Chi-Chih Yao: Quantum Circuit Complexity. FOCS 1993: 352-361
75 Jin-yi Cai, Richard J. Lipton, Robert Sedgewick, Andrew Chi-Chih Yao: Towards Uncheatable benchmarks. Structure in Complexity Theory Conference 1993: 2-11
74 Andrew Chi-Chih Yao: Groups and Algebraic Complexity (Abstract). WADS 1993: 35
73 Ravi Kannan, H. Venkateswaran, V. Vinay, Andrew Chi-Chih Yao: A Circuit-Based Proof of Toda's Theorem. Information and Computation 104(2): 271-276 (1993)1992
72 Andrew Chi-Chih Yao: Algebraic Decision Trees and Euler Characteristics. FOCS 1992: 268-277
71 Anders Björner, László Lovász, Andrew Chi-Chih Yao: Linear Decision Trees: Volume Estimates and Topological Bounds. STOC 1992: 170-1771991
70 Andrew Chi-Chih Yao: Recent Progress in Circuit and Communication Complexity (Abstract). FCT 1991: 104
69 Sampath Kannan, Andrew Chi-Chih Yao: Program Checkers for Probability Generation. ICALP 1991: 163-173
68 Andrew Chi-Chih Yao: Lower Bounds to Randomized Algorithms for Graph Properties. JCSS 42(3): 267-287 (1991)
67 Andrew Chi-Chih Yao: Lower Bounds for Algebraic Computation Trees with Integer Inputs. SIAM J. Comput. 20(4): 655-668 (1991)1990
66 Andrew Chi-Chih Yao: On ACC and Threshold Circuits. FOCS 1990: 619-627
65 Andrew Chi-Chih Yao: Coherent Functions and Program Checkers (Extended Abstract). STOC 1990: 84-94
64 Claire Kenyon, Andrew Chi-Chih Yao: On Evaluating Boolean Functions with Unreliable Tests. International Journal of Foundations of Computer Science 1(1): 1-10 (1990)1989
63 Andrew Chi-Chih Yao: Lower Bounds for Algebraic Computation Trees with Integer Inputs. FOCS 1989: 308-313
62 Andrew Chi-Chih Yao: Circuits and Local Computation. STOC 1989: 186-196
61 Ronald L. Graham, Andrew Chi-Chih Yao: On the Improbability of Reaching Byzantine Agreements (Preliminary Version). STOC 1989: 467-478
60 Andrew Chi-Chih Yao: On Selecting the k Largest with Median Tests. Algorithmica 4(2): 293-300 (1989)
59 Andrew Chi-Chih Yao: On the Complexity of Partial Order Productions. SIAM J. Comput. 18(4): 679-689 (1989)1988
58 Andrew Chi-Chih Yao: Near-Optimal Time-Space Tradeoff for Element Distinctness. FOCS 1988: 91-97
57 Andrew Chi-Chih Yao: Monotone Bipartite Graph Properties are Evasive. SIAM J. Comput. 17(3): 517-520 (1988)1987
56 Andrew Chi-Chih Yao: Lower Bounds to Randomized Algorithms for Graph Properties (Extended Abstract). FOCS 1987: 393-4001986
55 Andrew Chi-Chih Yao: How to Generate and Exchange Secrets (Extended Abstract). FOCS 1986: 162-1671985
54 Andrew Chi-Chih Yao: Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version). FOCS 1985: 1-10
53 Andrew Chi-Chih Yao, F. Frances Yao: A General Approach to d-Dimensional Geometric Queries (Extended Abstract). STOC 1985: 163-168
52 Andrew Chi-Chih Yao: On Optimal Arrangements of Keys with Double Hashing. J. Algorithms 6(2): 253-264 (1985)
51 EE Andrew Chi-Chih Yao: Uniform Hashing Is Optimal. JACM 32(3): 687-693 (1985)
50 Andrew Chi-Chih Yao, F. Frances Yao: On Fault-Tolerant Networks for Sorting. SIAM J. Comput. 14(1): 120-128 (1985)
49 Andrew Chi-Chih Yao: On the Expected Performance of Path Compression Algorithms. SIAM J. Comput. 14(1): 129-133 (1985)
48 Andrew Chi-Chih Yao: On the Complexity of Maintaining Partial Sums. SIAM J. Comput. 14(2): 277-288 (1985)
1983
47 Andrew Chi-Chih Yao: Lower Bounds by Probabilistic Arguments (Extended Abstract). FOCS 1983: 420-4281982
46 Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract). FOCS 1982: 160-164
45 Andrew Chi-Chih Yao: Theory and Applications of Trapdoor Functions (Extended Abstract). FOCS 1982: 80-91
44 Andrew Chi-Chih Yao: Space-Time Tradeoff for Answering Range Queries (Extended Abstract). STOC 1982: 128-136
43 J. Michael Steele, Andrew Chi-Chih Yao: Lower Bounds for Algebraic Decision Trees. J. Algorithms 3(1): 1-8 (1982)
42 EE Andrew Chi-Chih Yao: On Parallel Computation for the Knapsack Problem. JACM 29(3): 898-903 (1982)
41 Robert Sedgewick, Thomas G. Szymanski, Andrew Chi-Chih Yao: The Complexity of Finding Cycles in Periodic Functions. SIAM J. Comput. 11(2): 376-390 (1982)
40 Andrew Chi-Chih Yao, F. Frances Yao: On the Average-Case Complexity of Selecting the kth Best. SIAM J. Comput. 11(3): 428-447 (1982)
39 Andrew Chi-Chih Yao: On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems. SIAM J. Comput. 11(4): 721-736 (1982)
38 Andrew Chi-Chih Yao: On the Time-Space Tradeoff for Sorting with Linear Queries. TCS 19: 203-218 (1982)1981
37 Danny Dolev, Andrew Chi-Chih Yao: On the Security of Public Key Protocols (Extended Abstract). FOCS 1981: 350-357
36 Andrew Chi-Chih Yao: On the Parallel Computation for the Knapsack Problem. STOC 1981: 123-127
35 Andrew Chi-Chih Yao: The Entropic Limitations on VLSI Computations (Extended Abstract). STOC 1981: 308-311
34 Allan Borodin, Leonidas J. Guibas, Nancy A. Lynch, Andrew Chi-Chih Yao: Efficient Searching Using Partial Ordering. Information Processing Letters 12(2): 71-75 (1981)
33 EE Andrew Chi-Chih Yao: Should Tables Be Sorted? JACM 28(3): 615-628 (1981)
32 EE Andrew Chi-Chih Yao: A Lower Bound to Finding Convex Hulls. JACM 28(4): 780-787 (1981)
31 Andrew Chi-Chih Yao: An Analysis of a Memory Allocation Scheme for Implementing Stacks. SIAM J. Comput. 10(2): 398-403 (1981)1980
30 Andrew Chi-Chih Yao: A Note on the Analysis of Extendible Hashing. Information Processing Letters 11(2): 84-86 (1980)
29 Edward G. Coffman Jr., Kimming So, Micha Hofri, Andrew Chi-Chih Yao: A Stochastic Model of Bin-Packing. Information and Control 44(2): 105-115 (1980)
28 Andrew Chi-Chih Yao: An Analysis of (h, k, 1)-Shellsort. J. Algorithms 1(1): 14-50 (1980)
27 EE Richard J. Lipton, Arnold L. Rosenberg, Andrew Chi-Chih Yao: External Hashing Schemes for Collections of Data Structures. JACM 27(1): 81-95 (1980)
26 EE Andrew Chi-Chih Yao: New Algorithms for Bin Packing. JACM 27(2): 207-227 (1980)
25 EE Ronald L. Graham, Andrew Chi-Chih Yao, F. Frances Yao: Information Bounds Are Weak in the Shortest Distance Problem. JACM 27(3): 428-444 (1980)
24 Andrew Chi-Chih Yao, Ronald L. Rivest: On the Polyhedral Decision Problem. SIAM J. Comput. 9(2): 343-347 (1980)
23 Andrew Chi-Chih Yao: Bounds on Selection Networks. SIAM J. Comput. 9(3): 566-582 (1980)
22 EE Jon Louis Bentley, Bruce W. Weide, Andrew Chi-Chih Yao: Optimal Expected-Time Algorithms for Closest Point Problems. TOMS 6(4): 563-580 (1980)1979
21 Andrew Chi-Chih Yao: Some Complexity Questions Related to Distributive Computing (Preliminary Report). STOC 1979: 209-213
20 Robert Endre Tarjan, Andrew Chi-Chih Yao: Storing a Sparse Table. CACM 22(11): 606-611 (1979)
19 Andrew Chi-Chih Yao: A Note on a Conjecture of Kam and Ullman Concerning Statistical Databases. Information Processing Letters 9(1): 48-50 (1979)
18 Andrew Chi-Chih Yao: The Complexity of Pattern Matching for a Random String. SIAM J. Comput. 8(3): 368-387 (1979)1978
17 Andrew Chi-Chih Yao: Should Tables Be Sorted? (Extended Abstract). FOCS 1978: 22-27
16 Andrew Chi-Chih Yao, F. Frances Yao: On the Average-case Complexity of Selecting k-th Best. FOCS 1978: 280-289
15 Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Informatica 9: 159-170 (1978)
14 EE Andrew Chi-Chih Yao, Ronald L. Rivest: k+1 Heads Are Better than k. JACM 25(2): 337-340 (1978)
13 Andrew Chi-Chih Yao: On the Loop Switching Addressing Problem. SIAM J. Comput. 7(4): 515-523 (1978)1977
12 Andrew Chi-Chih Yao: Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). FOCS 1977: 222-227
11 Andrew Chi-Chih Yao, David Avis, Ronald L. Rivest: An Omega(n^2 log n) Lower Bound to the Shortest Paths Problem. STOC 1977: 11-171976
10 Andrew Chi-Chih Yao, F. Frances Yao: The Complexity of Searching an Ordered Random Table (Extended Abstract). FOCS 1976: 173-177
9 Andrew Chi-Chih Yao, Ronald L. Rivest: k+1 Heads Are Better than k. FOCS 1976: 67-70
8 Andrew Chi-Chih Yao: On the Average Behavior of Set Merging Algorithms (Extended Abstract). STOC 1976: 192-195
7 Jon Louis Bentley, Andrew Chi-Chih Yao: An Almost Optimal Algorithm for Unbounded Searching. Information Processing Letters 5(3): 82-87 (1976)
6 EE Andrew Chi-Chih Yao, Foong Frances Yao: Lower Bounds on Merging Networks. JACM 23(3): 566-571 (1976)
5 Andrew Chi-Chih Yao: On the Evaluation of Powers. SIAM J. Comput. 5(1): 100-103 (1976)1975
4 Andrew Chi-Chih Yao: On the Complexity of Comparison Problems using Linear Functions (Preliminary Report). FOCS 1975: 85-89
3 Andrew Chi-Chih Yao: On Computing the Minima of Quadratic Forms (Preliminary Report). STOC 1975: 23-26
2 Andrew Chi-Chih Yao: An O(|E| log log |V|) Algorithm for Finding Minimum Spanning Trees. Information Processing Letters 4(1): 21-23 (1975)1974
1 Andrew Chi-Chih Yao: Bounds on Selection Networks. FOCS 1974: 110-116
--------------------------------------------------------------------------------
PRINCETON UNIVERSITY'S ANDREW CHI CHIH YAO WINS THE ASSOCIATION FOR COMPUTING MACHINERY'S 2000 A. M. TURING AWARD
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/Press Release
Last Update: February 1, 2001
by Patrick J. De Blasi
Andrew Yao
Citation
For significant research contributions in Computational Complexity, Analysis of Algorithms, Data Structures, Communication Complexity, and Cryptographic Protocols.ACM/Fellows Award. Last Update: September 11, 1998 by Patrick J. De Blasi
