Mihalis Yannakakis

Le diplôme d'ingénieur électricien que Mihalis Yannakakis a obtenu de l'Université technique nationale d'Athènes en 1975 a marqué le début d'une longue carrière dans la théorie de la complexité de calcul. Né en 1953 à Athènes, il a ensuite obtenu un doctorat en informatique à l'Université de Princeton, influençant par la suite la théorie des bases de données, la vérification et la théorie des graphes algorithmique.

Fondements de la complexité

Yannakakis a passé plus de deux décennies dans la recherche industrielle, débutant son mandat aux Laboratoires Bell en 1978. Il y a occupé le poste de directeur du département de recherche sur les principes informatiques de 1991 à 2001. Au cours de cette période, il a collaboré avec Christos Papadimitriou en 1988 pour définir les classes de complexité Max-NP et Max-SNP, fournissant une explication rigoureuse des limitations observées dans l'approximation des problèmes NP-difficiles tels que le problème du voyageur de commerce et 3SAT. Ses travaux de 1993 avec Carsten Lund ont permis de clarifier davantage la difficulté inhérente au calcul de solutions approchées pour des problèmes de minimisation tels que la coloration de graphes.

Innovations dans les bases de données

Ses contributions à la théorie des bases de données se sont concentrées sur l'optimisation du traitement des requêtes par l'étude des schémas acycliques. Il a introduit l'algorithme de Yannakakis pour les requêtes conjonctives acycliques, démontrant que ces structures pouvaient être résolues en temps polynomial. Au-delà de l'optimisation des requêtes, il a étudié les politiques de verrouillage, prouvant que la sécurité des bases de données pouvait être maintenue en dehors des contraintes rigides du verrouillage en deux phases en utilisant la structure d'hypergraphe des données et les contraintes de cohérence des transactions pour éviter les interblocages.

Vérification et leadership académique

Passant au monde académique, Yannakakis a occupé un poste de professeur à l'Université Stanford en 2002 avant de rejoindre l'Université Columbia en 2004. Il est actuellement professeur de sciences informatiques Percy K. et Vida L. W. Hudson. Ses recherches en vérification assistée par ordinateur ont établi des fondements algorithmiques pour tester la logique temporelle à temps linéaire et les diagrammes de séquence de messages. Il a également développé la vérification de modèles adaptatifs aux côtés d'Alex Groce et Doron Peled, une méthode qui affine les modèles de systèmes en fonction des résultats de la vérification.

Reconnaissance professionnelle

Yannakakis a maintenu une présence éditoriale importante, ayant été rédacteur en chef du SIAM Journal on Computing entre 1998 et 2003. Son statut académique se reflète dans ses adhésions à la National Academy of Sciences, à la National Academy of Engineering, à l'American Academy of Arts and Sciences et à l'Academia Europaea. Ses récompenses comprennent le prix Knuth en 2005 et le prix de théorie John von Neumann en 2023.

En bref

- Naissance : 1953, Athènes, Grèce - Doctorat : Université de Princeton, 1979 - Prix Knuth : 2005 - Prix de théorie John von Neumann : 2023 - Fellow de l'ACM : 1998 - Nationalité : États-Unis ; Grèce - Langues : grec moderne

Questions des lecteurs

### Qu'est-ce que l'algorithme de Yannakakis ?

C'est une méthode utilisée pour exécuter des requêtes conjonctives acycliques dans les systèmes de bases de données, permettant de les résoudre en temps polynomial.

### À quelles institutions Yannakakis a-t-il été affilié ?

Il a travaillé aux Laboratoires Bell, aux Laboratoires Avaya, à l'Université Stanford et à l'Université Columbia.