Trouver le vrai potentiel des algorithmes

Chaque semestre, la professeure agrégée Virginia Vassilevska Williams tente de transmettre une leçon fondamentale à ses étudiants de premier cycle en informatique : Les mathématiques sont la base de tout.

Souvent, les étudiants viennent dans la classe de Williams, 6.006 (Introduction to Algorithms), voulant plonger dans la programmation avancée qui alimente les plus récentes et les plus grandes techniques de calcul. Ses leçons se concentrent plutôt sur la façon dont les algorithmes sont conçus autour de modèles et de concepts mathématiques de base.

 » Lorsqu’ils suivent un cours d’algorithmique, de nombreux étudiants s’attendent à programmer beaucoup et peut-être à utiliser un apprentissage approfondi, mais c’est très mathématique et il y a très peu de programmation « , dit M. Williams, qui a récemment obtenu la permanence au Département de génie électrique et d’informatique.  » Nous n’avons pas beaucoup de temps ensemble en classe (seulement deux heures par semaine), mais j’espère que pendant ce temps, ils pourront voir un peu de la beauté des mathématiques – parce que les mathématiques permettent de voir comment et pourquoi tout fonctionne ensemble. C’est vraiment une belle chose. »

La vie de Williams est très influencée par les mathématiques. Enfant de deux parents mathématiciens, elle est tombée très tôt amoureuse du sujet. Mais même si elle excellait dans cette matière, ses cours au lycée se concentraient sur l’allemand, l’écriture et la biologie. Retournant à ses premières amours au collège et au-delà, elle a appliqué ses compétences en mathématiques pour faire des vagues en informatique.

Dans des travaux très influents, Williams a amélioré en 2012 un algorithme pour la  » multiplication matricielle  » – une opération fondamentale en informatique – qui était considérée comme l’itération la plus rapide depuis 24 ans. Des années plus tard, elle a cofondé un domaine émergent appelé  » complexité à grain fin « , qui cherche à expliquer, en partie, à quelle vitesse certains algorithmes peuvent résoudre divers problèmes.

Dans le domaine de la multiplication matricielle, son travail s’est maintenant légèrement déplacé pour montrer que les techniques existantes  » ne peuvent pas faire mieux « , dit-elle. « Nous ne pouvions plus améliorer les performances de nos propres algorithmes, alors nous avons trouvé des moyens d’expliquer pourquoi nous ne pouvions pas et pourquoi les autres méthodes ne peuvent pas non plus améliorer les performances. »

Chemin d’enroulement vers les mathématiques

Ayant grandi à Sofia, en Bulgarie, Williams aimait les mathématiques et était un étudiant doué. Mais ses parents lui ont souvent rappelé que la vie de mathématicien n’était pas vraiment glamour – surtout lorsqu’il s’agit de trouver des postes de professeur dans le même secteur pour deux personnes. Ils voyageaient parfois là où le travail les emmenait.

Cela comprenait une brève odyssée autour des États-Unis quand j’étais enfant. Le premier arrêt était à Laramie, Wyoming. Ses parents étaient professeurs invités à l’Université du Wyoming, tandis que Williams a d’abord eu du mal à passer en quatrième année à cause de la barrière de la langue. « Je ne parlais pas vraiment anglais, et j’ai été jeté dans cette école. Mon frère et moi avons appris l’anglais en regardant la chaîne Disney, ce qui était assez amusant « , dit Williams, qui parle aujourd’hui le bulgare, l’anglais, l’allemand et un peu de russe.

Le prochain arrêt était Los Angeles – juste au moment des émeutes de Rodney King. « La maison de l’autre côté de notre rue a été incendiée », se souvient Williams. « C’était des souvenirs très étranges de L.A. »

De retour en Bulgarie après deux ans, Williams a décidé  » d’explorer ses options  » en dehors des mathématiques en s’inscrivant au lycée de langue allemande de Sofia, le meilleur lycée du pays à l’époque, où elle a étudié la langue allemande, la littérature, l’histoire et d’autres sujets de sciences humaines. Mais, quand il s’agissait de s’inscrire à l’université, elle ne pouvait jamais se débarrasser de son premier amour. « J’ai vraiment essayé d’aimer les sciences humaines, et ce que j’ai appris m’est très utile aujourd’hui. Mais ces sujets étaient très difficiles pour moi. Mon cerveau ne fonctionne tout simplement pas de cette façon, dit-elle. « Je suis retourné à ce que j’aime. »

Transfixés par des algorithmes

En 1999, Williams s’est inscrit à Caltech. Au cours de sa deuxième année, elle a été séduite par un nouveau domaine passionnant : l’informatique. « J’ai suivi mon premier cours de programmation, et j’ai adoré ça « , dit-elle.

Elle a été subjuguée par les algorithmes de multiplication matricielle, qui ont un fond de maths robustes. Ces algorithmes calculent plusieurs tableaux de nombres correspondant à certaines données et produisent une matrice combinée unique de certaines valeurs cibles. Les applications sont très variées, notamment l’infographie, la conception de produits, l’intelligence artificielle et la biotechnologie.

En tant que doctorante à Carnegie Mellon, et au-delà, elle a publié nombreux articlessur des sujets tels que le développement d’algorithmes de multiplication matricielle rapide dans des structures algébriques spéciales, avec des applications incluant la programmation de vols et le routage de réseaux. Après avoir obtenu son doctorat, elle a occupé une série de postes de post-doc et de chercheur à l’Institute for Advanced Study, à l’Université de Californie à Berkeley et à l’Université de Stanford, où elle a obtenu un poste de professeur en 2013 pour donner des cours sur les algorithmes.

En 2012, elle a développé un nouvel algorithme plus rapide que l’algorithme Coppersmith-Winograd, qui régnait en maître dans la multiplication des matrices depuis les années 1980. La méthode de Williams a réduit le nombre d’étapes nécessaires pour multiplier les matrices. Son algorithme n’est que légèrement plus lent que le détenteur du record actuel.

Faire face à la complexité

Entre 2010 et 2015, Mme Williams et son mari, Ryan Williams, qui est également professeur au MIT, sont devenus les principaux fondateurs de la  » complexité à grain fin « . Le domaine plus ancien de la  » complexité informatique  » trouve des algorithmes dont l’efficacité est prouvée et des algorithmes qui sont probablement inefficaces, en fonction d’un certain seuil d’étapes de calcul qu’ils prennent pour résoudre un problème.

La complexité à grain fin regroupe les problèmes par équivalence de calcul pour mieux prouver si les algorithmes sont vraiment optimaux ou non. Par exemple, deux problèmes peuvent apparaître très différents dans ce qu’ils résolvent et dans le nombre d’étapes que les algorithmes prennent pour les résoudre. Mais une complexité fine montre que de tels problèmes sont secrètement les mêmes. Par conséquent, si un algorithme existe pour un problème qui utilise moins d’étapes, alors il doit exister un algorithme pour l’autre problème qui utilise moins d’étapes, et vice versa. En revanche, s’il existe un algorithme optimal prouvé pour un problème, alors tous les problèmes équivalents doivent avoir des algorithmes optimaux. Si jamais quelqu’un trouve un algorithme beaucoup plus rapide pour un problème, tous les problèmes équivalents peuvent être résolus plus rapidement.

Depuis le lancement conjoint du terrain,  » c’est gonflé « , dit Williams. « Pour la plupart des conférences d’informatique théorique, vous pouvez maintenant soumettre votre article sous la rubrique ‘complexité fine’. »

En 2017, Mme Williams est arrivée au MIT, où elle dit avoir trouvé des chercheurs passionnés et partageant les mêmes idées. De nombreux étudiants diplômés et collègues, par exemple, travaillent sur des sujets liés à la complexité à grain fin. En retour, ses élèves lui ont fait découvrir d’autres matières, comme la cryptographie, où elle introduit maintenant des idées d’une complexité fine.

Elle étudie aussi parfois le  » choix social computationnel « , un domaine qui a attiré son attention pendant ses études supérieures. Ses travaux portent sur l’examen de la complexité de calcul nécessaire pour truquer les jeux de sport, les systèmes de vote et autres systèmes où les concurrents sont placés entre parenthèses appariées. Si quelqu’un sait, par exemple, quel joueur gagnera dans les matchs par paires, un organisateur de tournoi peut placer tous les joueurs à des positions spécifiques dans le classement initial pour s’assurer qu’un certain joueur gagne tout.

La simulation de toutes les combinaisons possibles pour truquer ces schémas peut être très complexe sur le plan du calcul. Mais Williams, un joueur de tennis passionné, a écrit un papier qui a trouvé qu’il est assez simple de truquer un tournoi à élimination directe pour qu’un certain joueur gagne, en fonction de prédictions précises pour les vainqueurs des matchs et d’autres facteurs.

Cette année, elle a co-écrit un papier qui montrait qu’un organisateur de tournoi pouvait organiser un semis initial et soudoyer certains joueurs de haut niveau – dans le cadre d’un budget spécifique – pour s’assurer qu’un joueur favori gagne le tournoi.  » Quand j’ai besoin de faire une pause dans mon travail habituel, je travaille dans ce domaine « , dit Williams. « C’est un changement de rythme amusant. »

Grâce à l’omniprésence de l’informatique aujourd’hui, les étudiants diplômés de Mme Williams entrent souvent dans sa classe avec une expérience en informatique bien plus grande qu’elle ne l’était à leur âge. Mais pour les aider à s’orienter dans une voie distincte, elle s’inspire de ses propres expériences au collège, en s’accrochant à des sujets précis qu’elle poursuit encore aujourd’hui.

 » Pour faire une bonne recherche, il faut être obsédé par un problème « , dit Williams. « Je veux qu’ils trouvent quelque chose dans mon cours qui les obsède. »