title: Mihalis Yannakakis
text: # Mihalis Yannakakis
  
  Mihalis Yannakakis est un chercheur en informatique, né le 13 septembre 1953 à Athènes. Il est actuellement professeur à l'université Columbia. Il est connu notamment pour ses travaux sur la théorie de la complexité et sur les bases de données. Il a reçu le prix Knuth en 2005 et le prix EATCS en 2020.
  
  ## Biographie
  
  Mihalis Yannakakis a reçu son PhD à l'université de Princeton en 1978 sous la direction de Jeffrey David Ullman. Il a été rédacteur-en-chef du journal SIAM Journal on Computing de 1998 à 2003.
  
  ## Travaux
  
  La notice du prix Knuth indique comme travaux important :
  
  * en complexité : la définition de la classe max-SNP (voir APX) et des travaux sur la difficulté d'approximation des problèmes de coloration de graphe et de couverture par ensembles;
  * en théorie des bases de données;
  * en vérification formelle, notamment pour les algorithmes de model checking.
  