Mihalis Yannakakis
chercheur en informatique
Pour les articles homonymes, voir Yannakakis.
Mihalis Yannakakis est un chercheur en informatique, né le à 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[1] et le prix EATCS en 2020.
Mihalis Yannakakis
Mihalis Yannakakis en 2006
| Naissance | |
|---|---|
| Nom dans la langue maternelle |
Μιχάλης Γιαννακάκης |
| Nationalités | |
| Formation | |
| Activité |
| A travaillé pour | |
|---|---|
| Membre de | |
| Directeur de thèse | |
| Distinctions |
ACM Fellow () Prix Knuth () |
Biographie
modifierMihalis Yannakakis a reçu son PhD à l'université de Princeton en 1978 sous la direction de Jeffrey David Ullman[2]. Il a été rédacteur-en-chef du journal SIAM Journal on Computing de 1998 à 2003[3].
Travaux
modifierLa notice du prix Knuth[1] indique comme travaux important :
- en complexité : la définition de la classe max-SNP (voir APX)[4] et des travaux sur la difficulté d'approximation des problèmes de coloration de graphe et de couverture par ensembles[5];
- en théorie des bases de données;
- en vérification formelle, notamment pour les algorithmes de model checking.
Notes et références
modifier- page du prix Knuth
- (en) « Mihalis Yannakakis », sur le site du Mathematics Genealogy Project.
- « New Editors-in-Chief for SIAP, SICOMP, and SIDMA », sur SIAM, .
- Christos H. Papadimitriou et Mihalis Yannakakis, « Optimization, Approximation, and Complexity Classes (Extended Abstract) », dans Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, , p. 229-234
- Carsten Lund et Mihalis Yannakakis, « On the hardness of approximating minimization problems », dans Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, , p. 286-293
Liens externes
modifier- Page personnelle à l'université Columbia
- Ressources relatives à la recherche :
