Dr Andrew Ch-Chi Yao of 2021 Kyoto Prize

In this lecture, I would like to give a brief account of my journey through computer science. It is the story of a young physicist in the 1970s who, like Alice in Wonderland, stumbled into the world of computer science by chance and started a long magical journey thereafter.

I was born in Shanghai, China in 1946; later my family moved to Hong Kong, then Taiwan. My upbringing carries the traditional Chinese value and adores scholarship and culture. As a kid I loved math, science and history. Science, like history, gave me a sense of awe and magnificence with its stories of adventure, brilliance and courage. I dreamed that this would also be my destiny!

After obtaining a Ph.D. in Physics from Harvard in 1972, I by chance came across the then “novel” subject of computer science. Feeling an instant attraction, I decided to switch fields and obtained a second degree.

My research initially focused on solving open problems in algorithms such as minimum spanning tree, B-trees, etc. I gravitated toward developing new computing frameworks and theories after 1975. The research typically starts out by framing a question that interests me intensely. Indeed, I have come to believe that asking the right question is often the key to good research.

I will give a synopsis of some of my work by discussing three topics: Minmax complexity, Communication complexity and Multi-party secure computation. I will also say a brief word about quantum computing, auction theory and AI. It is gratifying that these works have apparently stood the test of time: they are seeing continued strong research interest today and, in some cases, even having practical impact.

No doubt, the diverse and colorful subjects mentioned above reflect the blossoming of Information Science over the last 50 years, and its growing interdisciplinary connections today.

To sum up, I have had a wonderful journey in computer science with many twists and turns! Along the way, I have encountered many extraordinary talents, and made good friends. I am especially fortunate to have had two inspiring mentors, Prof. Glashow and Prof. Knuth. Scientific giants aside, they are also the kindest and most gracious human beings ever!

Biography:

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.