Alumnus Yao Wins 2021 Kyoto Prize for Novel Theory of Computation and Communication

Illinois CS alumnus Andrew Chi-Chih Yao (PhD CS '75) has won the 2021 Kyoto Prize, a highly prestigious international award honoring those who have contributed significantly to the fields of science and technology, arts, and philosophy. He was recognized for pioneering contributions to a new theory of computation and communication and a fundamental theory for its security.

The Inamori Foundation made the announcement in June 2021. Each laureate will receive a diploma, Kyoto Prize gold medal, and 100 million yen (approximately $908,000 in U.S. currency).

Yao, who is dean of the Institute for Interdisciplinary Information Sciences at Tsinghua University, has developed innovative theoretical models for computation and communication that have influenced multiple fields, including security, privacy, parallel computing, big data processing, and quantum computing.

“I feel deeply honored to be named as recipient of the Kyoto Prize in Advanced Technology by the Inamori Foundation this year,” Yao said in a media release from the Foundation. “Dr. Kazuo Inamori dedicates himself to the betterment of mankind and stress[es] the essential roles for both science and humanities in moving toward that goal. His vision touches me profoundly. The Foundation recognizes achievements that are considered exemplary in this regard, and I am thrilled to join the list of distinguished laureates who have received this honor previously.”

In 1977, Yao established a principle in problem solving by a computational algorithm, called 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.

In 1979, he 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. He also provided a novel method for its analysis.

The theory of communication complexity was a highly original, new concept that sent strong ripples through the computational theory research community, providing a theoretical foundation for other important models such as circuit complexity, parallel and distributed computing, data structures and stream computing.

Since then, 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, which provided the standard model of evaluating the security of communication methods.

In 1982, he introduced computational entropy into Shannon’s theory of communication quantity and the theory of communication security. 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 and computational theory.

In addition, he examined a mathematically complete model for communication-based secure computation protocols, and proposed an innovative secure computational method facilitating secure computation by many individuals, including adversaries, while preserving the privacy of the information pertaining to each individual.

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 the conditions that must be satisfied to ensure information privacy and security. Remarkably, this model illustrated the principles of secure computation with an efficiency approaching that of a single binary circuit. This was a landmark achievement in the field of information security.

Yao’s concept and principle of quantum communication complexity enable quantitative performance evaluation of quantum computing.

Due to worldwide government restrictions related to the pandemic, there will not be a prize presentation ceremony. However, Yao and the other 2021 laureates will deliver special online lectures, according to the Kyoto Prize website.

Other scientists with ties to the University of Illinois have won the Kyoto Prize, including:

• Chemistry professor Paul Lauterbur (1994), who was the first to propose the basic principles of magnetic resonance imaging (MRI), experimentally confirmed its feasibility, and developed many related technologies.
• Electrical engineering alumnus Jack Kilby (1993), who was the first to propose the fundamental concept of the monolithic integrated circuit (IC). Kilby demonstrated the IC concept by mounting transistors, resistors and capacitors all on a single semiconductor substrate.

In 2000, Yao received the A.M. Turing Award, considered the Nobel Prize of computing, for his groundbreaking contributions to the theory of computation.

This article was adapted from the Kyoto Prize website.