Virginia Vassilevska Williams

Modèle:Infobox Biographie2 Virginia Vassilevska Williams, née Virginia Panayotova VassilevskaModèle:Références multiples, est une informaticienne théoricienne et mathématicienne, spécialiste en théorie des algorithmes et théorie de la complexité informatique. Elle est, depuis juillet 2022, professeure titulaire en informatique au Massachusetts Institute of TechnologyModèle:Références multiples.

Formation et carrière

Virginia Williams est originaire de Bulgarie et a fréquenté un lycée allemand à SofiaModèle:Références multiples. Elle est diplômée du California Institute of Technology en 2003 et a complété son Ph. D. à l'Université Carnegie-Mellon en 2008Modèle:Références multiples. Sa thèse, intitulée Efficient Algorithms for Path Problems in Weighted Graphs, a été dirigée par Guy BlellochModèle:Références multiples.

Après des recherches postdoctorales à l'Institute for Advanced Study et à l'Université de Californie à Berkeley, Virginia Williams est devenu professeur assistant en informatique à l'Université Stanford en 2013Modèle:Références multiples. Elle a rejoint le MIT en tant que professeur associé en 2017Modèle:Références multiples.

Recherche

Virginia Williams a obtenu des résultats remarquables pour la complexité de la multiplication de matricesModèle:Références multiples ; elle travaille sur les algorithmes dynamiquesModèle:Références multiples et elle a contribué au développement du domaine de la complexité à grain finModèle:Références multiples.

En 2011, Virginia Williams décrit un algorithme permettant de multiplier deux matrices $n\times n$ en temps $O(n^{2,373})$. L'exposant $2,373$ améliore l'exposant $2,3755$ d'un précédent algorithme de multiplication matricielle, l'algorithme Coppersmith-Winograd, qui alors était le meilleur algorithme connu depuis 24 ans. Son amélioration initiale est indépendante de celle d'Andrew Stothers, qui avait également amélioré la borne de Coppersmith-Winograd un an plus tôt en donnant l'exposant $2,3737$ ; après avoir appris le travail de Stothers, elle a combiné les idées des deux méthodes pour améliorer également sa propre borneModèle:Références multiples. En 2020, elle donne avec Josh Alman l'algorithme de multiplication matricielle le plus rapide connu jusqu'en 2022, en temps $O(n^{2,3728596})$Modèle:Références multiples.

En 2025, elle présente, avec Josh Alman, Ran Duan, Yinzhan Xu, Zixuan Xu et Renfei Zhou, un nouvel algorithme dont l'exposant est majoré par $2,371339$.

Distinctions

Virginia Williams est NSF Computing Innovation Fellow de 2009 à 2011Modèle:Références multiples et obtient une bourse de recherche Sloan en 2017Modèle:Références multiples. Elle est conférencière invitée au Congrès international des mathématiciens de 2018 à Rio de Janeiro, dans la section sur les aspects mathématiques de l'informatiqueModèle:Références multiples.

Note

Virginia Williams est la fille des mathématiciens appliqués Panayot Vassilevski et Tanya Kostova-VassilevskaModèle:Références multiples. Elle est mariée avec Ryan Williams, également professeur d'informatique au MIT ; ils travaillent aussi ensemble dans le domaine de la complexité fineModèle:Références multiples.

Liens externes

• Page d'accueil