title: Andrew Yao
text: # Andrew Yao
  
  Andrew Chi-Chih Yao (chinois : 姚期智; pinyin : Yáo Qīzhì), né à Shanghai le 24 décembre 1946, est un chercheur en informatique. Il a reçu le prix Knuth en 1996 et le prix Turing en 2000.
  
  ## Biographie
  
  Andrew Yao est né à Shanghai le 24 décembre 1946. Il a vécu ses premières années à Hong Kong puis à Taïwan.
  
  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 et en informatique de l'université de l'Illinois à Urbana-Champaign en 1975, sous la direction de Chung Laung Liu.
  
  Il a travaillé au MIT à l'université de Californie à Berkeley et à l'université Stanford avant d'être professeur à l'université de Princeton 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.
  
  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 Table Be Sorted. Il a amélioré la complexité en temps de la recherche d'un arbre couvrant de poids $minimal^,.$
  
  Il a aussi jeté les bases de la complexité de la communication, dans l'article Some Complexity Questions Related to Distributed Computing, et travaillé sur les circuits booléens.
  
  ## Distinctions
  
  Après le prix Knuth en 1996, 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.
  
  Il reçoit le prix de Kyoto en 2021.
  
  