Andrew Yao
chercheur en informatique
From Wikipedia, the free encyclopedia
Andrew Chi-Chih Yao (chinois : 姚期智; pinyin : Yáo Qīzhì), né à Shanghai le , est un chercheur en informatique. Il a reçu le prix Knuth en 1996 et le prix Turing en 2000.
Université de l'Illinois à Urbana-Champaign
Université nationale de Taïwan
Lycée Chien Kuo de Taipei (en)
| Naissance | |
|---|---|
| Nationalité |
chinoise (depuis ) |
| Formation |
Université Harvard Université de l'Illinois à Urbana-Champaign Université nationale de Taïwan Lycée Chien Kuo de Taipei (en) |
| Activités | |
| Conjoint |
| A travaillé pour | |
|---|---|
| Membre de |
Association for Computing Machinery () Académie américaine des sciences (- Académie américaine des sciences () Division des sciences informatiques de l'Académie chinoise des sciences (d) () Académie américaine des arts et des sciences Academia sinica |
| Directeur de thèse |
Chung Laung Liu (en) |
| Site web | |
| Distinctions |
Prix Turing () Liste détaillée Prix George-Pólya () Bourse Guggenheim () ACM Fellow () Prix Knuth () Prix Turing () Docteur honoris causa de l'université chinoise de Hong Kong () Docteur honoris causa de l'université de Waterloo () IACR Fellow () Prix de Kyoto en technologies avancée () Docteur honoris causa de l'université polytechnique de Hong Kong |
Biographie
Andrew Yao est né à Shanghai le . Il a vécu ses premières années à Hong Kong puis à Taïwan[1].
Il a fait son premier cycle universitaire en physique à l'université nationale de Taïwan. Il a obtenu un doctorat en physique de l'université Harvard en 1972, sous la direction de Sheldon Glashow[2] et en informatique de l'université de l'Illinois à Urbana-Champaign en 1975, sous la direction de Chung Laung Liu[3].
Il a travaillé au MIT à l'université de Californie à Berkeley et à l'université Stanford avant d'être professeur à l'université de Princeton[2] et à l'université Tsinghua.
Travaux
De façon générale, il a fait avancer de très nombreux domaines de l'informatique théorique[2].
En cryptographie et en sécurité, on lui doit par exemple modèle de Dolev-Yao (en) et le problème du millionnaire (en).
En algorithmique plus classique, il a été le premier à utiliser l'algorithme minimax pour prouver ce que l'on nomme le principe de Yao, un outil permettant d'étudier les algorithmes probabilistes. Il a aussi travaillé sur les structures de données, en utilisant notamment la théorie de Ramsey dans l'article Should Tables Be Sorted[4]. Il a amélioré la complexité en temps de la recherche d'un arbre couvrant de poids minimal[2],[5].
Il a aussi jeté les bases de la complexité de la communication[2], dans l'article Some Complexity Questions Related to Distributed Computing[6], et travaillé sur les circuits booléens.
Distinctions
Après le prix Knuth en 1996[2], il a reçu le prix Turing en 2000 pour ses contributions en théorie de la calculabilité, génération de nombres pseudo-aléatoires, cryptographie et complexité de la communication[1].
Il reçoit le prix de Kyoto en 2021[7].
