Pour les articles homonymes, voirYao.
| Naissance | |
|---|---|
| Nationalités | américaine(jusqu'en) chinoise  |
| Formation | |
| 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 |
Andrew Chi-Chih Yao (chinois : 姚期智;pinyin : Yáo Qīzhì), né àShanghai le, est un chercheur eninformatique. Il a reçu leprix Knuth en 1996 et leprix Turing en 2000.
Andrew Yao est né à Shanghai le. Il a vécu ses premières années àHong Kong puis àTaïwan[1].
Il a fait sonpremier cycle universitaire enphysique à l'université nationale de Taïwan. Il a obtenu undoctorat en physique de l'université Harvard en 1972, sous la direction deSheldon Glashow[2] et eninformatique de l'université de l'Illinois à Urbana-Champaign en 1975, sous la direction de Chung Laung Liu[3].
Il a travaillé auMIT à l'université de Californie à Berkeley et à l'université Stanford avant d'êtreprofesseur à l'université de Princeton[2] et à l'université Tsinghua.
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 exemplemodèle de Dolev-Yao (en) et leproblème du millionnaire (en).
En algorithmique plus classique, il a été le premier à utiliser l'algorithme minimax pour prouver ce que l'on nomme leprincipe de Yao, un outil permettant d'étudier lesalgorithmes probabilistes. Il a aussi travaillé sur lesstructures de données, en utilisant notamment lathéorie de Ramsey dans l'articleShould Tables Be Sorted[4]. Il a amélioré lacomplexité en temps de la recherche d'unarbre couvrant de poids minimal[2],[5].
Il a aussi jeté les bases de lacomplexité de la communication[2], dans l'articleSome Complexity Questions Related to Distributed Computing[6], et travaillé sur lescircuits booléens.
Après leprix Knuth en 1996[2], il a reçu leprix Turing en 2000 pour ses contributions en théorie de la calculabilité, génération de nombres pseudo-aléatoires,cryptographie etcomplexité de la communication[1].
Il reçoit leprix de Kyoto en 2021[7].
: :
