Virginia Vassilevska Williams

Virginia Williams est originaire de Bulgarie et a fréquenté un lycée allemand à Sofia^[3]. Elle est diplômée du California Institute of Technology en 2003 et a complété son Ph. D. à l'Université Carnegie-Mellon en 2008^[1]. Sa thèse, intitulée Efficient Algorithms for Path Problems in Weighted Graphs, a été dirigée par Guy Blelloch^[4].

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 2013^[1]. Elle a rejoint le MIT en tant que professeur associé en 2017^[2].

Virginia Williams a obtenu des résultats remarquables pour la complexité de la multiplication de matrices^[5] ; elle travaille sur les algorithmes dynamiques^[6] et elle a contribué au développement du domaine de la complexité à grain fin^[7].

En 2011, Virginia Williams décrit un algorithme permettant de multiplier deux matrices ${\displaystyle n\times n}$ en temps ${\displaystyle O(n^{2,373})}$. L'exposant ${\displaystyle 2,373}$ améliore l'exposant ${\displaystyle 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 ${\displaystyle 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 borne^[8],[5]. En 2020, elle donne avec Josh Alman l'algorithme de multiplication matricielle le plus rapide connu jusqu'en 2022, en temps ${\displaystyle O(n^{2,3728596})}$^[9].

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 ${\displaystyle 2,371339}$^[10].

Virginia Williams est NSF Computing Innovation Fellow de 2009 à 2011^[1] et obtient une bourse de recherche Sloan en 2017^[2]. 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'informatique^[11].

Virginia Williams est la fille des mathématiciens appliqués Panayot Vassilevski et Tanya Kostova-Vassilevska^[12]. Elle est mariée avec Ryan Williams, également professeur d'informatique au MIT ; ils travaillent aussi ensemble dans le domaine de la complexité fine^[3].