Andrew Chi-Chih Yao

Andrew Chi-Chih Yao created new trends in computer science and made a great contribution to cutting-edge research in various areas, especially in security, secure computing, and quantum computation through establishing innovative fundamental theories for computation and communication. His achievements are continuing to influence current real-world problems such as security, secure computing, and big data processing.

Andrew Chi-Chih Yao has constructed innovative theoretical models for computation and communication, creating trends in modern computational theory that have revolutionized computational theory from a communications perspective. Further afield, Yao’s research has influenced computer science in multiple fields, including security, privacy, parallel computing, and quantum computing.

In 1977, Yao first established a principle in problem solving by a computational algorithm, known as Yao’s minimax principle, as the basis of worst case complexity of randomized algorithms in comparison with deterministic algorithms using von Neumann’s minimax theorem (1). In 1979, Yao presented a model in which two persons perform cooperative computation through communication and introduced the concept of communication complexity, a measure of the difficulty of a computational problem in terms of the communication load (2). Furthermore, he provided a novel method for its analysis. The theory of communication complexity was an original, new concept providing a theoretical foundation for many important models such as circuit complexity, parallel and distributed computing, and stream computing. As such, Yao’s work has inspired many recent breakthroughs in computational complexity theory.

Subsequently, Yao’s research has evolved into theories that consider the security and privacy of communications. In 1981, he contributed to a theoretical definition of complete security (i.e., the Dolev-Yao model) for information and communication systems using public-key cryptography and provided the standard model of evaluating the security of communication methods (3). In 1982, building on computational aspects, he introduced computational entropy into Shannon’s theory of communication quantity and the theory of communication security (4). He then applied this concept to quantify the safety of security using unidirectional functions, thereby providing a computational method for testing (Yao’s test) pseudo-random number generation, which bears significance for cryptography.

In addition, he examined a model for communication-basedsecure computation protocols, and proposed a secure computational method facilitating secure computation by many individuals, including adversaries, while preserving the privacy of the information pertaining to each individual (5). Here, using insights into so-called Yao’s millionaires’ problem, in which “two wealthy people determine which of them owns the larger fortune without disclosing their wealth to each other,” he presented a rigorous model of information privacy and security. This was a landmark achievement in the field of information security.

Yao’s work has provided essential concepts and models that play a vital role in modern society. These concepts and models are most evident in areas such as in e-commerce and crypto-asset management. Moreover, Yao’s concept and principle of quantum communication complexity enable quantitative performance evaluation of quantum computing (6). These achievements have a great impact and ripple effect on the information science field, and therefore Yao truly deserves the Kyoto Prize.

For these reasons, the Inamori Foundation is pleased to present the 2021 Kyoto Prize in Advanced Technology to Andrew Chi-Chih Yao.

References
(1) Yao AC-C (1977) Probabilistic computations: Toward a unified measure of complexity. In Proceedings of IEEE 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), IEEE: 222–227.
(2) Yao AC-C (1979) Some Complexity Questions Related to Distributive Computing (Preliminary Report) In Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC ’79), ACM: 209–213.
(3) Dolev D & Yao AC-C (1983) On the security of public key protocols. IEEE Transactions on Information Theory 29 (2): 198–208.
(4) Yao AC-C (1982) Theory and Applications of Trapdoor Functions. In Proceedings of IEEE 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), IEEE: 80–91.
(5) Yao AC-C (1982) Protocols for Secure Computations. In Proceedings of IEEE 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), IEEE: 160–164.
(6) Yao AC-C (1993) Quantum Circuit Complexity. In Proceedings of IEEE 34th Annual Symposium on Foundations of Computer Science (FOCS 1993), IEEE: 352–361.