Andrew Yao
Encyclopedia
Andrew Chi-Chih Yao is a prominent computer scientist
and computational theorist. Yao used the minimax theorem
to prove what is now known as Yao's Principle
.
Yao was born in Shanghai
, China
. He completed his undergraduate education in physics
at the National Taiwan University
, before completing a Doctor of Philosophy
in physics at Harvard University
in 1972, and then a second PhD in computer science
from the University of Illinois at Urbana-Champaign
in 1975.
In 1996 he was awarded the Knuth Prize
. He received the Turing Award
, the most prestigious award in computer science, in 2000, "in recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation, cryptography
, and communication complexity
".
From 1982 to 1986, he was a full professor at Stanford University
. From 1986 to 2004, he was the William and Edna Macaleer Professor of Engineering and Applied Science at Princeton University
, where he continued to work on algorithms and complexity. In 2004, he became a Professor of the Center for Advanced Study, Tsinghua University (CASTU)
and the director of the Institute for Theoretical Computer Science (ITCS)
, Tsinghua University
in Beijing
. He now is the Distinguished Professor-at-Large in the Chinese University of Hong Kong
.
He is a member of U.S. National Academy of Sciences
, a fellow
of the American Academy of Arts and Sciences
, a fellow of the American Association for the Advancement of Science
, a fellow of the Association for Computing Machinery
, and a foreign member of Chinese Academy of Sciences
. His wife, Frances Yao
, is also a well-known theoretical computer scientist.
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
and computational theorist. Yao used the minimax theorem
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
to prove what is now known as Yao's Principle
Yao's Principle
In computational complexity theory, Yao's principle or Yao's minimax principle states that the expected cost of any randomized algorithm for solving a given problem, on the worst case input for that algorithm, can be no better than the expected cost, for a worst-case random probability distribution...
.
Yao was born in Shanghai
Shanghai
Shanghai is the largest city by population in China and the largest city proper in the world. It is one of the four province-level municipalities in the People's Republic of China, with a total population of over 23 million as of 2010...
, China
China
Chinese civilization may refer to:* China for more general discussion of the country.* Chinese culture* Greater China, the transnational community of ethnic Chinese.* History of China* Sinosphere, the area historically affected by Chinese culture...
. He completed his undergraduate education in physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
at the National Taiwan University
National Taiwan University
National Taiwan University is a national co-educational university located in Taipei, Republic of China . In Taiwan, it is colloquially known as "Táidà" . Its main campus is set upon 1,086,167 square meters in Taipei's Da'an District. In addition, the university has 6 other campuses in Taiwan,...
, before completing a Doctor of Philosophy
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
in physics at Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
in 1972, and then a second PhD in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
from the University of Illinois at Urbana-Champaign
University of Illinois at Urbana-Champaign
The University of Illinois at Urbana–Champaign is a large public research-intensive university in the state of Illinois, United States. It is the flagship campus of the University of Illinois system...
in 1975.
In 1996 he was awarded the Knuth Prize
Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...
. He received the Turing Award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
, the most prestigious award in computer science, in 2000, "in recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation, cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, and communication complexity
Communication complexity
The notion of communication complexity was introduced by Yao in 1979,who investigated the following problem involving two separated parties . Alice receives an n-bit string x and Bob another n-bit string y, and the goal is for one of them to compute a certain function f with the least amount of...
".
From 1982 to 1986, he was a full professor at Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
. From 1986 to 2004, he was the William and Edna Macaleer Professor of Engineering and Applied Science at Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
, where he continued to work on algorithms and complexity. In 2004, he became a Professor of the Center for Advanced Study, Tsinghua University (CASTU)
Center for Advanced Study, Tsinghua University
The Center for Advanced Study, Tsinghua University is a research institute established in Beijing in 1997. Modelled after the Princeton-based Institute for Advanced Study, albeit in a university setting, it is engaged in theoretical studies in physics, computer science and biology...
and the director of the Institute for Theoretical Computer Science (ITCS)
Institute for Theoretical Computer Science
The Institute for Theoretical Computer Science is a scholastic research institute headed by Professor Andrew Chi-Chih Yao at Tsinghua University in Beijing....
, Tsinghua University
Tsinghua University
Tsinghua University , colloquially known in Chinese as Qinghua, is a university in Beijing, China. The school is one of the nine universities of the C9 League. It was established in 1911 under the name "Tsinghua Xuetang" or "Tsinghua College" and was renamed the "Tsinghua School" one year later...
in Beijing
Beijing
Beijing , also known as Peking , is the capital of the People's Republic of China and one of the most populous cities in the world, with a population of 19,612,368 as of 2010. The city is the country's political, cultural, and educational center, and home to the headquarters for most of China's...
. He now is the Distinguished Professor-at-Large in the Chinese University of Hong Kong
Chinese University of Hong Kong
The Chinese University of Hong Kong is a research-led university in Hong Kong.CUHK is the only tertiary education institution in Hong Kong with Nobel Prize winners on its faculty, including Chen Ning Yang, James Mirrlees, Robert Alexander Mundell and Charles K. Kao...
.
He is a member of U.S. National Academy of Sciences
United States National Academy of Sciences
The National Academy of Sciences is a corporation in the United States whose members serve pro bono as "advisers to the nation on science, engineering, and medicine." As a national academy, new members of the organization are elected annually by current members, based on their distinguished and...
, a fellow
Fellow
A fellow in the broadest sense is someone who is an equal or a comrade. The term fellow is also used to describe a person, particularly by those in the upper social classes. It is most often used in an academic context: a fellow is often part of an elite group of learned people who are awarded...
of the American Academy of Arts and Sciences
American Academy of Arts and Sciences
The American Academy of Arts and Sciences is an independent policy research center that conducts multidisciplinary studies of complex and emerging problems. The Academy’s elected members are leaders in the academic disciplines, the arts, business, and public affairs.James Bowdoin, John Adams, and...
, a fellow of the American Association for the Advancement of Science
American Association for the Advancement of Science
The American Association for the Advancement of Science is an international non-profit organization with the stated goals of promoting cooperation among scientists, defending scientific freedom, encouraging scientific responsibility, and supporting scientific education and science outreach for the...
, a fellow of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
, and a foreign member of Chinese Academy of Sciences
Chinese Academy of Sciences
The Chinese Academy of Sciences , formerly known as Academia Sinica, is the national academy for the natural sciences of the People's Republic of China. It is an institution of the State Council of China. It is headquartered in Beijing, with institutes all over the People's Republic of China...
. His wife, Frances Yao
Frances Yao
Frances Foong Yao is professor and head of the department of computer science at the City University of Hong Kong.After receiving a B.S. in mathematics from National Taiwan University in 1969, Yao did her Ph.D. studies under the supervision of Michael J. Fischer at the Massachusetts Institute of...
, is also a well-known theoretical computer scientist.
See also
- Important publications in cryptography
- Yao's test
- Yao's Millionaires' ProblemYao's Millionaires' ProblemYao's Millionaires' problem is a secure multiparty communication problem which was introduced by Andrew Yao, a prominent computer scientist and computational theorist...