A.M. TURING CENTENARY CELEBRATION WEBCAST
  • go to Robert W. Floyd's profile page
  • go to Kenneth Lane Thompson's profile page
  • go to Ole-Johan Dahl 's profile page
  • go to Butler W Lampson's profile page
  • go to Dana S Scott's profile page
  • go to Silvio Micali's profile page
  • go to Jim Gray 's profile page
  • go to Stephen A Cook's profile page
  • go to Avi Wigderson's profile page
  • go to Herbert A. Simon's profile page
  • go to Leonard M. Adleman's profile page
  • go to Kristen Nygaard 's profile page
  • go to John E Hopcroft's profile page
  • go to Allen Newell 's profile page
  • go to C. Antony R. Hoare 's profile page
  • go to Alfred V Aho's profile page
  • go to Amir Pnueli's profile page
  • go to Raj Reddy's profile page
  • go to Shafi Goldwasser 's profile page
  • go to Jeffrey D Ullman's profile page
  • go to Robert E Tarjan's profile page
  • go to Robert E Kahn's profile page
  • go to John McCarthy's profile page
  • go to Geoffrey E Hinton's profile page
A.M. TURING AWARD WINNERS BY...
Andrew C Yao

Andrew Chi-Chih Yao DL Author Profile link

China – 2000
Short Annotated Bibliography
  1. Yao, Andrew Chi-Chih, “Probabilistic Computations: Toward a Unified Measure of Complexity” (Extended Abstract), 18th Annual Symposium on Foundations of Computer Science (FOCS ’77), IEEE Computer Society, 1977, pp. 222-227. This paper considers probability in computation from two perspectives: probability distributions on inputs, and the use randomization in algorithms. The two perspectives are unified with Yao’s min-max principle, which states that the worst-case expected running time of a randomized algorithm for a problem is equal to the average-case running time of any deterministic algorithm, for the worst-case distribution on problem inputs.
  2. Yao, Andrew Chi-Chih, “Should Tables Be Sorted?” (Extended Abstract), 19th Annual Symposium on Foundations of Computer Science (FOCS ’78). IEEE Computer Society, 1978, pp. 22-27. In this paper Yao introduces the cell-probe model for the analysis of data structures in which the cost of a computation is the number of accesses to a random access memory with cell size log n.
  3. Yao, Andrew Chi-Chih, “Some Complexity Questions Related to Distributive Computing” (Preliminary Report), Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC ’79), ACM Press, 1979, pp. 209-213, available here.
  4. Yao, Andrew Chi-Chih, “Quantum Circuit Complexity,” 34th Annual Symposium on Foundations of Computer Science (FOCS ’93), IEEE Computer Society, 1993, pp. 352-361. The first of these two papers introduces communication complexity, a measure which has proven to be useful in obtaining complexity bounds in areas including parallel computation, circuits, and data structures. The second paper extends the classical model of the first paper to situations in which participants in a protocol may exchange quantum bits.
  5. Yao, Andrew Chi-Chih, “Protocols for Secure Computations” (Extended Abstract), 23rd Annual Symposium on Foundations of Computer Science (FOCS ’82), IEEE Computer Society, 1982, pp. 160-164.
  6. Yao, Andrew Chi-Chih, “How to Generate and Exchange Secrets” (Extended Abstract), 27th Annual Symposium on Foundations of Computer Science (FOCS ’87), IEEE Computer Society, 1986, pp. 162-167. The first of these two papers introduces secure function evaluation, and gives a protocol for the famous Millionaires’ Problem. In talks related to these papers Yao introduced a technique for secure computation known as garbled circuits.
  7. Yao, Andrew Chi-Chih, “Theory and Applications of Trapdoor Functions” (Extended Abstract), 23rd Annual Symposium on Foundations of Computer Science (FOCS ’82), IEEE Computer Society, 1982, pp. 80-91. This influential paper introduces a number of notions and techniques that are essential to modern complexity-based cryptography, including computational indistinguishability as a basis for characterizing pseudorandom generators, and the use of one-way functions as a complexity-theoretic basis for obtaining cryptographic security via pseudorandomness. Yao also introduces ideas which have had a major impact in other areas such as computational information theory and derandomization.
  8. Dolev, Danny and Andrew Chi-Chih Yao, “On the security of public key protocols,” IEEE Transactions on Information Theory, Vol. 29, Num. 2, 1983, pp. 198-207. The authors introduce a model for the analysis of cryptography-based security protocols which has become known as the Dolev-Yao model, and is the basis for many current approaches to formal verification of such protocols.
  9. Steele, J. Michael and Andrew Chi-Chih Yao, “Lower Bounds for Algebraic Decision Trees,” Journal of Algorithms, Vol. 3, Num. 1, 1982, pp. 1-8.
  10. Yao, Andrew Chi-Chih, “Lower Bounds to Randomized Algorithms for Graph Properties,” Journal of Computing Systems Science, Vol. 42, Num. 3, 1991, pp.  267-287. Professor Yao has made extensive contributions to structured models of computation, including decision trees. The first of these two papers proposes algebraic decision trees, a generalization of the linear decision trees of Dobkin and Lipton. The second paper considers randomization in the Boolean decision tree model for deciding graph properties.